In this paper we explore some connections between some combinatorial properties of words and the study of extremal cases of the automata minimization process. An intermediate role is played by the notion od word trees for which some properties of words are generalized. In particular, we describe an infinite family of binary automata, called word automata and constructed by using standard sturmian words and more specifically Fibonacci words, that represent the extremal case of some well known automata minimization algorithms, such as Moore’s and Hopcroft’s methods. As well as giving an overview of the main results in this context, the main purpose of this paper is to prove that, even if a recently introduced polynomial variants of Brzozowski’s algorithm is considered, such family of word automata represent the worst case for the number of steps and for its overall time complexity. This fact suggests that the standard sturmian words, and consequently the associated word automata, are able to capture some properties for which the minimization process becomes inherently more complex.
Castiglione, G., Sciortino, M. (2013). Words, Trees and Automata Minimization. In J. Karhumäki, A. Lepistö, L. Zamboni (a cura di), Combinatorics on Words - 9th International Conference, WORDS 2013, Turku, Finland, September 16-20, 2013, Proceedings (pp. 18-33). Springer-Verlag Berlin Heidelberg 2013 [10.1007/978-3-642-40579-2_6].
Words, Trees and Automata Minimization
CASTIGLIONE, Giuseppa;SCIORTINO, Marinella
2013-01-01
Abstract
In this paper we explore some connections between some combinatorial properties of words and the study of extremal cases of the automata minimization process. An intermediate role is played by the notion od word trees for which some properties of words are generalized. In particular, we describe an infinite family of binary automata, called word automata and constructed by using standard sturmian words and more specifically Fibonacci words, that represent the extremal case of some well known automata minimization algorithms, such as Moore’s and Hopcroft’s methods. As well as giving an overview of the main results in this context, the main purpose of this paper is to prove that, even if a recently introduced polynomial variants of Brzozowski’s algorithm is considered, such family of word automata represent the worst case for the number of steps and for its overall time complexity. This fact suggests that the standard sturmian words, and consequently the associated word automata, are able to capture some properties for which the minimization process becomes inherently more complex.File | Dimensione | Formato | |
---|---|---|---|
[25]words2013.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
274.63 kB
Formato
Adobe PDF
|
274.63 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.