TY - CHAP
T1 - Hopcroft’s Algorithm and Cyclic Automata
AU - Restivo, Antonio
AU - Castiglione, Giuseppa
AU - Sciortino, Marinella
PY - 2008
Y1 - 2008
N2 - Minimization of deterministic finite automata is a largely studied problem of the Theory of Automata and Formal Languages. It consists in finding the unique (up to isomorphism) minimal deterministic automaton recognizing a set of words. The first approaches to this topic can be traced back to the 1950’s with the works of Huffman and Moore (cf. [12,15]). Over the years several methods to solve this problem have been proposed but the most efficient algorithm in the worst case was given by Hopcroft in [11]. Such an algorithm computes in O(n log n) the minimal automaton equivalent to a given automaton with n states. The Hopcroft’s algorithm has been widely studied, described and implemented by many authors (cf. [13,4,16,2]). In particular, in [4] the worst case of the algorithm is considered. The authors of [4] introduce an infinite family of automata associated to circular words. The circular words taken into account are the de Bruijn words, and, by using the associated automata, it is shown that the complexity of the algorithm is tight. More precisely, the Hopcroft’s algorithm has some degrees of freedom (see Section 3) in the sense that there can be several executions of the algorithm on a given deterministic automaton. The running time of such executions can be different. With regard to the family of automata proposed in [4] it is shown that there exist some “unlucky” sequences of choices that slow down the computation to achieve the bound Ω(nlogn). However, there are also executions that run in linear time for the same automata. The authors of [4] leave the open problem whether there are automata on which all the executions of Hopcroft’s algorithm do not run in linear time. In [16] the author proves that the exact worst case (i.e. in terms of the exact number of operations) of the algorithm for unary languages is reached only for the family of automata given in [4] when a queue is used in the implementation. He remarks that a stack implementation is more convenient for such automata. At the same time in [16] the author conjectures that there is a strategy for processing the stack used in the implementation such that the minimization of all unary languages will be realized in linear time by the Hopcroft’s algorithm.
AB - Minimization of deterministic finite automata is a largely studied problem of the Theory of Automata and Formal Languages. It consists in finding the unique (up to isomorphism) minimal deterministic automaton recognizing a set of words. The first approaches to this topic can be traced back to the 1950’s with the works of Huffman and Moore (cf. [12,15]). Over the years several methods to solve this problem have been proposed but the most efficient algorithm in the worst case was given by Hopcroft in [11]. Such an algorithm computes in O(n log n) the minimal automaton equivalent to a given automaton with n states. The Hopcroft’s algorithm has been widely studied, described and implemented by many authors (cf. [13,4,16,2]). In particular, in [4] the worst case of the algorithm is considered. The authors of [4] introduce an infinite family of automata associated to circular words. The circular words taken into account are the de Bruijn words, and, by using the associated automata, it is shown that the complexity of the algorithm is tight. More precisely, the Hopcroft’s algorithm has some degrees of freedom (see Section 3) in the sense that there can be several executions of the algorithm on a given deterministic automaton. The running time of such executions can be different. With regard to the family of automata proposed in [4] it is shown that there exist some “unlucky” sequences of choices that slow down the computation to achieve the bound Ω(nlogn). However, there are also executions that run in linear time for the same automata. The authors of [4] leave the open problem whether there are automata on which all the executions of Hopcroft’s algorithm do not run in linear time. In [16] the author proves that the exact worst case (i.e. in terms of the exact number of operations) of the algorithm for unary languages is reached only for the family of automata given in [4] when a queue is used in the implementation. He remarks that a stack implementation is more convenient for such automata. At the same time in [16] the author conjectures that there is a strategy for processing the stack used in the implementation such that the minimization of all unary languages will be realized in linear time by the Hopcroft’s algorithm.
KW - Hopcroft's algorithm
KW - Sturmian words
KW - Hopcroft's algorithm
KW - Sturmian words
UR - http://hdl.handle.net/10447/47220
M3 - Chapter
SN - 978-3-540-88281-7
T3 - Lecture Notes in Computer Science
SP - 172
EP - 183
BT - Language and Automata Theory and Applications
ER -