New tools for state complexity
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 n...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2020-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4835/pdf |
| _version_ | 1797270041191776256 |
|---|---|
| author | Pascal Caron Edwin Hamel-De le court Jean-Gabriel Luque Bruno Patrou |
| author_facet | Pascal Caron Edwin Hamel-De le court Jean-Gabriel Luque Bruno Patrou |
| author_sort | Pascal Caron |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:57Z |
| format | Article |
| id | doaj.art-e07e275edcb34b56a3bd699e19acd64c |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:57Z |
| publishDate | 2020-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-e07e275edcb34b56a3bd699e19acd64c2024-03-07T15:40:51ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502020-03-01vol. 22 no. 1Automata, Logic and Semantics10.23638/DMTCS-22-1-94835New tools for state complexityPascal CaronEdwin Hamel-De le courtJean-Gabriel LuqueBruno PatrouA 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.https://dmtcs.episciences.org/4835/pdfcomputer science - formal languages and automata theory |
| spellingShingle | Pascal Caron Edwin Hamel-De le court Jean-Gabriel Luque Bruno Patrou New tools for state complexity Discrete Mathematics & Theoretical Computer Science computer science - formal languages and automata theory |
| title | New tools for state complexity |
| title_full | New tools for state complexity |
| title_fullStr | New tools for state complexity |
| title_full_unstemmed | New tools for state complexity |
| title_short | New tools for state complexity |
| title_sort | new tools for state complexity |
| topic | computer science - formal languages and automata theory |
| url | https://dmtcs.episciences.org/4835/pdf |
| work_keys_str_mv | AT pascalcaron newtoolsforstatecomplexity AT edwinhameldelecourt newtoolsforstatecomplexity AT jeangabrielluque newtoolsforstatecomplexity AT brunopatrou newtoolsforstatecomplexity |