The study of some close connections between the combinatorial properties of words and the performance of the automata minimization process constitutes the main focus of this paper. These relationships have been, in fact, the basis of the study of the tightness and the extremal cases of Hopcroft's algorithm, that is, up to now, the most efficient minimization method for deterministic finite state automata. Recently, increasing attention has been paid to another minimization method that, unlike the approach proposed by Hopcroft, is not based on refinement of the set of states of the automaton, but on automata operations such as determinization and reverse, and is also applicable to non-deterministic finite automata. However, even for deterministic automata, it was proved that the method incurs, almost surely, in an explosion of the number of the states. Very recently, some polynomial variants of Brzozowski's method have been introduced. In this paper, by using some combinatorial properties of words, we analyze the performance of one of such algorithms when applied to a particular infinite family of automata, called standard word automata, constructed by using standard sturmian words. In particular, Θ( nlog n) is the worst case time complexity when the algorithm is applied to the infinite family of word automata associated to Fibonacci words representing also the worst case of Hopcroft's minimization algorithm.

Castiglione, G., Sciortino, M. (2015). Standard Sturmian words and automata minimization algorithms. THEORETICAL COMPUTER SCIENCE, 601, 58-66 [10.1016/j.tcs.2015.07.023].

Standard Sturmian words and automata minimization algorithms

CASTIGLIONE, Giuseppa;SCIORTINO, Marinella
2015-01-01

Abstract

The study of some close connections between the combinatorial properties of words and the performance of the automata minimization process constitutes the main focus of this paper. These relationships have been, in fact, the basis of the study of the tightness and the extremal cases of Hopcroft's algorithm, that is, up to now, the most efficient minimization method for deterministic finite state automata. Recently, increasing attention has been paid to another minimization method that, unlike the approach proposed by Hopcroft, is not based on refinement of the set of states of the automaton, but on automata operations such as determinization and reverse, and is also applicable to non-deterministic finite automata. However, even for deterministic automata, it was proved that the method incurs, almost surely, in an explosion of the number of the states. Very recently, some polynomial variants of Brzozowski's method have been introduced. In this paper, by using some combinatorial properties of words, we analyze the performance of one of such algorithms when applied to a particular infinite family of automata, called standard word automata, constructed by using standard sturmian words. In particular, Θ( nlog n) is the worst case time complexity when the algorithm is applied to the infinite family of word automata associated to Fibonacci words representing also the worst case of Hopcroft's minimization algorithm.
2015
Castiglione, G., Sciortino, M. (2015). Standard Sturmian words and automata minimization algorithms. THEORETICAL COMPUTER SCIENCE, 601, 58-66 [10.1016/j.tcs.2015.07.023].
File in questo prodotto:
File Dimensione Formato  
TCS 2015.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 361.27 kB
Formato Adobe PDF
361.27 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/203380
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact