HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

New tools for state complexity

Pascal Caron 1, 2 Edwin Hamel-de Le Court 1, 2 Jean-Gabriel Luque 1, 2 Bruno Patrou 1, 2
1 CA - LITIS - Equipe Combinatoire et algorithmes
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Contributor : Pascal Caron Connect in order to contact the contributor
Submitted on : Tuesday, April 2, 2019 - 2:17:56 PM
Last modification on : Wednesday, March 2, 2022 - 10:10:10 AM

Links full text


  • HAL Id : hal-02087923, version 1
  • ARXIV : 1807.00663


Pascal Caron, Edwin Hamel-de Le Court, Jean-Gabriel Luque, Bruno Patrou. New tools for state complexity. 2019. ⟨hal-02087923⟩



Record views