New tools for state complexity
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1
Voir la notice de l'article provenant de la source Episciences
A monster is an automaton in which every function from states to states is represented by at least one letter. A modifier is a set of functions allowing one to transform a set of automata into one automaton. We revisit some language transformation algorithms in terms of modifier and monster. These new theoretical concepts allow one to find easily some state complexities. We illustrate this by retrieving the state complexity of the Star of Intersection and the one of the Square root operation.
@article{DMTCS_2020_22_1_a6,
author = {Caron, Pascal and court, Edwin Hamel-De le and Luque, Jean-Gabriel and Patrou, Bruno},
title = {New tools for state complexity},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {22},
number = {1},
year = {2020-2021},
doi = {10.23638/DMTCS-22-1-9},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-9/}
}
TY - JOUR AU - Caron, Pascal AU - court, Edwin Hamel-De le AU - Luque, Jean-Gabriel AU - Patrou, Bruno TI - New tools for state complexity JO - Discrete mathematics & theoretical computer science PY - 2020-2021 VL - 22 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-9/ DO - 10.23638/DMTCS-22-1-9 LA - en ID - DMTCS_2020_22_1_a6 ER -
%0 Journal Article %A Caron, Pascal %A court, Edwin Hamel-De le %A Luque, Jean-Gabriel %A Patrou, Bruno %T New tools for state complexity %J Discrete mathematics & theoretical computer science %D 2020-2021 %V 22 %N 1 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-9/ %R 10.23638/DMTCS-22-1-9 %G en %F DMTCS_2020_22_1_a6
Caron, Pascal; court, Edwin Hamel-De le; Luque, Jean-Gabriel; Patrou, Bruno. New tools for state complexity. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi: 10.23638/DMTCS-22-1-9
Cité par Sources :