TY - JOUR

T1 - Standard Sturmian words and automata minimization algorithms

AU - Castiglione, Giuseppa

AU - Sciortino, Marinella

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Automata minimization

KW - Brzozowski's minimization algorithm

KW - Computer Science (all)

KW - Standard Sturmian words

KW - Theoretical Computer Science

KW - Automata minimization

KW - Brzozowski's minimization algorithm

KW - Computer Science (all)

KW - Standard Sturmian words

KW - Theoretical Computer Science

UR - http://hdl.handle.net/10447/203380

UR - http://www.journals.elsevier.com/theoretical-computer-science/

M3 - Article

VL - 601

SP - 58

EP - 66

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -