{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T14:59:47Z","timestamp":1782917987686,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540882817","type":"print"},{"value":"9783540882824","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-88282-4_17","type":"book-chapter","created":{"date-parts":[[2008,9,24]],"date-time":"2008-09-24T07:46:38Z","timestamp":1222242398000},"page":"172-183","source":"Crossref","is-referenced-by-count":11,"title":["Hopcroft\u2019s Algorithm and Cyclic Automata"],"prefix":"10.1007","author":[{"given":"Giusi","family":"Castiglione","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antonio","family":"Restivo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"17_CR1","unstructured":"Almeida, M., Moreira, N., Reis, R.: On the performance of automata minimization algorithms. Technical Report DCC-2007-03, Universidade do Porto (2007)"},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/11812128_12","volume-title":"Implementation and Application of Automata","author":"M. Baclet","year":"2006","unstructured":"Baclet, M., Pagetti, C.: Around Hopcroft\u2019s algorithm. In: H. Ibarra, O., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol.\u00a04094, pp. 114\u2013125. Springer, Heidelberg (2006)"},{"key":"17_CR3","unstructured":"B\u00e9al, M.-P., Crochemore, M.: Minimizing local automata. In: ISIT 2007 (to appear, 2007)"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-540-30500-2_4","volume-title":"Implementation and Application of Automata","author":"J. Berstel","year":"2005","unstructured":"Berstel, J., Carton, O.: On the complexity of Hopcroft\u2019s state minimization algorithm. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 35\u201344. Springer, Heidelberg (2005)"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1051\/ita:2005038","volume":"450","author":"J.P. Borel","year":"2006","unstructured":"Borel, J.P., Reutenauer, C.: On Christoffel classes. RAIRO-Theoretical Informatics and Applications\u00a0450, 15\u201328 (2006)","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"key":"17_CR6","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata"},{"key":"17_CR7","unstructured":"Champarnaud, J.-M., Khorsi, A., Paranthon, T.: Split and join for minimizing: Brzozowskis algorithm. In: Proceedings of PSC 2002 (Prague Stringology Conference), pp. 96\u2013104 (2002)"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.3115\/1611533.1611538"},{"key":"17_CR9","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol.\u00a0A (1974)"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF00264025","volume":"2","author":"D. Gries","year":"1973","unstructured":"Gries, D.: Describing an algorithm by Hopcroft. Acta Inf.\u00a02, 97\u2013109 (1973)","journal-title":"Acta Inf."},{"key":"17_CR11","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"Theory of machines and computations (Proc. Internat. Sympos. Technion, Haifa, 1971)","author":"J.E. Hopcroft","year":"1971","unstructured":"Hopcroft, J.E.: An nlogn algorithm for mimimizing the states in a finite automaton. In: Paz, A., Kohavi, Z. (eds.) Theory of machines and computations (Proc. Internat. Sympos. Technion, Haifa, 1971), pp. 189\u2013196. Academic Press, New York (1971)"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0016-0032(54)90574-8","volume":"257","author":"D.A. Huffman","year":"1954","unstructured":"Huffman, D.A.: The synthesis of sequencial switching circuits. J. Franklin Institute\u00a0257, 161\u2013190 (1954)","journal-title":"J. Franklin Institute"},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0304-3975(99)00150-4","volume":"250","author":"T. Knuutila","year":"2001","unstructured":"Knuutila, T.: Re-describing an algorithm by Hopcroft. Theoret.Comput. Sci.\u00a0250, 333\u2013363 (2001)","journal-title":"Theoret.Comput. Sci."},{"key":"17_CR14","unstructured":"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)"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Moore, E.F.: Gedaken experiments on sequential machines. In: Automata Studies, pp. 129\u2013153 (1956)","DOI":"10.1515\/9781400882618-006"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Paun, A.: On the Hopcroft\u2019s minimization algorithm. CoRR, abs\/0705.1986 (2007)","DOI":"10.1145\/1283920.1283943"},{"issue":"1","key":"17_CR17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D. Revuz","year":"1992","unstructured":"Revuz, D.: Minimisation of acyclic deterministic automata in linear time. Theor. Comput. Sci.\u00a092(1), 181\u2013189 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR18","unstructured":"Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences, http:\/\/www.research.att.com\/~njas\/sequences\/"},{"key":"17_CR19","unstructured":"Tabakov, D., Vardi, M.Y.: Experimental evaluation of classical automata constructions"},{"key":"17_CR20","unstructured":"Vajda, S.: Fibonacci and Lucas numbers, and the golden section. Technical Report 98\/183, Ellis Horwood Ltd., Chichester (1989)"},{"key":"17_CR21","unstructured":"Watson, B.: A taxonomy of finite automata minimization algorithms. Technical Report 93\/44, Eindhoven University of Technology, Faculty of Mathematics and Computing Science (1994)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88282-4_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T02:04:23Z","timestamp":1738375463000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-88282-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540882817","9783540882824"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88282-4_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}