×

Hopcroft’s algorithm and cyclic automata. (English) Zbl 1163.68021

Martín-Vide, Carlos (ed.) et al., Language and automata theory and applications. Second international conference, LATA 2008, Tarragona, Spain, March 13–19, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-88281-7/pbk). Lecture Notes in Computer Science 5196, 172-183 (2008).
Hopcroft’s famous algorithm [J. Hopcroft, “An \(n\log n\) algorithm for minimizing states in a finite automaton”, Theory of machines and computations. Proc. Internat. Sympos., Technion, Haifa, 1971. New York: Academic Press. 189–196 (1971; Zbl 0293.94022)] builds, from a finite automaton, the unique minimal (in the number of states) automaton recognizing the same language. Roughly, this algorithm iteratively divides equivalence classes of states by computing the pre-image of a class under \(a\)-transitions for some letter \(a\) of the alphabet. This algorithm is non-deterministic since it allows for flexibility such as choosing the class and the letter at each step of the iteration. Since the run time of these various executions can be different, it is interesting to consider not only the worst-case complexity but also to see if it could be possible to reduce the run time by making appropriate choices.
For instance, while J. Berstel and O. Carton [“On the complexity of Hopcroft’s state minimization algorithm”, Lect. Notes Comput. Sci. 3317, 35–44 (2005; Zbl 1115.68417)] exhibit a family of automata allowing executions of Hopcroft’s algorithm in time \(\Omega(n\log n)\), there are, for the same family, executions which run in linear time.
This paper exhibits a family of automata for which the run time is \(\Theta(n\log n)\) for any execution of Hopcroft’s algorithm. To show this, the authors consider a unary automaton (single letter alphabet) associated with circular words. The techniques used further develop the ideas of Berstel and Carton [loc. cit.].
For the entire collection see [Zbl 1148.68005].

MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Almeida, M., Moreira, N., Reis, R.: On the performance of automata minimization algorithms. Technical Report DCC-2007-03, Universidade do Porto (2007)
[2] Baclet, M.; Pagetti, C.; H. Ibarra, O.; Yen, H.-C., Around Hopcroft’s algorithm, Implementation and Application of Automata, 114-125 (2006), Heidelberg: Springer, Heidelberg · Zbl 1160.68399 · doi:10.1007/11812128_12
[3] Béal, M.-P., Crochemore, M.: Minimizing local automata. In: ISIT 2007 (to appear, 2007)
[4] Berstel, J.; Carton, O.; Domaratzki, M.; Okhotin, A.; Salomaa, K.; Yu, S., On the complexity of Hopcroft’s state minimization algorithm, Implementation and Application of Automata, 35-44 (2005), Heidelberg: Springer, Heidelberg · Zbl 1115.68417
[5] Borel, J. P.; Reutenauer, C., On Christoffel classes, RAIRO-Theoretical Informatics and Applications, 450, 15-28 (2006) · Zbl 1085.68116 · doi:10.1051/ita:2005038
[6] Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata · Zbl 0116.33605
[7] Champarnaud, J.-M., Khorsi, A., Paranthon, T.: Split and join for minimizing: Brzozowskis algorithm. In: Proceedings of PSC 2002 (Prague Stringology Conference), pp. 96-104 (2002)
[8] Daciuk, J., Watson, R.E., Watson, B.W.: Incremental construction of acyclic finite-state automata and transducers. In: Finite State Methods in Natural Language Processing, Bilkent University, Ankara, Turkey (1998) · Zbl 1232.68081
[9] Eilenberg, S.: Automata, Languages, and Machines, vol. A (1974) · Zbl 0317.94045
[10] Gries, D., Describing an algorithm by Hopcroft, Acta Inf., 2, 97-109 (1973) · Zbl 0242.94042
[11] Hopcroft, J. E.; Paz, A.; Kohavi, Z., An nlogn algorithm for mimimizing the states in a finite automaton, Theory of machines and computations (Proc. Internat. Sympos. Technion, Haifa, 1971), 189-196 (1971), New York: Academic Press, New York · Zbl 0266.94019
[12] Huffman, D. A., The synthesis of sequencial switching circuits, J. Franklin Institute, 257, 161-190 (1954) · Zbl 0166.27201 · doi:10.1016/0016-0032(54)90574-8
[13] Knuutila, T., Re-describing an algorithm by Hopcroft, Theoret.Comput. Sci., 250, 333-363 (2001) · Zbl 0952.68077 · doi:10.1016/S0304-3975(99)00150-4
[14] Matz, O., Miller, A., Potthoff, A., Thomas, W., Valkema, E.: Report on the program AMoRE. Technical Report 9507, Inst. f. Informatik u.Prakt. Math., CAU Kiel (1995)
[15] Moore, E.F.: Gedaken experiments on sequential machines. In: Automata Studies, pp. 129-153 (1956)
[16] Paun, A.: On the Hopcroft’s minimization algorithm. CoRR, abs/0705.1986 (2007)
[17] Revuz, D., Minimisation of acyclic deterministic automata in linear time, Theor. Comput. Sci., 92, 1, 181-189 (1992) · Zbl 0759.68066 · doi:10.1016/0304-3975(92)90142-3
[18] Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/ njas/sequences/ · Zbl 1044.11108
[19] Tabakov, D., Vardi, M.Y.: Experimental evaluation of classical automata constructions · Zbl 1143.68443
[20] Vajda, S.: Fibonacci and Lucas numbers, and the golden section. Technical Report 98/183, Ellis Horwood Ltd., Chichester (1989) · Zbl 0695.10001
[21] Watson, B.: A taxonomy of finite automata minimization algorithms. Technical Report 93/44, Eindhoven University of Technology, Faculty of Mathematics and Computing Science (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.