New tools for state complexity
Edwin Hamel-De Le Court  1@  , Pascal Caron  1, *@  , Jean-Gabriel Luque  1, *@  , Bruno Patrou  1, *@  
1 : Laboratoire dÍnformatique, de Traitement de lÍnformation et des Systèmes  (LITIS)  -  Site web
Université de Rouen Normandie
Avenue de lÚniversité 76800 Saint-Étienne-du-Rouvray -  France
* : Auteur correspondant

The state complexity of a rational language is the size of its minimal automaton and the one of a rational operation is the maximal one of those languages obtained by applying this operation onto languages of fixed state complexities. A monster is an automaton in which every function from states to states is represented by at least one letter. In this paper, we study applications called modifiers that transform a tuple of automata into one in such a way that the state complexity of the associated rational operation can be found looking only at monsters.
By describing some well-known rational operations as modifiers, we retrieve easily the state complexity of the Star of Intersection and the one of the Square root operation, improving for this last result the upper-bound given by Maslov.


Personnes connectées : 1