Geodesic
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.
DOI : 10.23638/DMTCS-22-1-9
Classification : 68Q45 
@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. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-9/

Cité par Sources :