{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:55:02Z","timestamp":1766066102425},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,10,12]],"date-time":"2011-10-12T00:00:00Z","timestamp":1318377600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9557-7","type":"journal-article","created":{"date-parts":[[2011,10,11]],"date-time":"2011-10-11T17:16:39Z","timestamp":1318353399000},"page":"509-531","source":"Crossref","is-referenced-by-count":10,"title":["Average Case Analysis of Moore\u2019s State Minimization Algorithm"],"prefix":"10.1007","volume":"63","author":[{"given":"Fr\u00e9d\u00e9rique","family":"Bassino","sequence":"first","affiliation":[]},{"given":"Julien","family":"David","sequence":"additional","affiliation":[]},{"given":"Cyril","family":"Nicaud","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,12]]},"reference":[{"key":"9557_CR1","first-page":"129","volume-title":"Automata Studies","author":"E.F. Moore","year":"1956","unstructured":"Moore, E.F.: Gedanken experiments on sequential machines. In: Automata Studies, pp. 129\u2013153. Princeton University Press, Princeton (1956)"},{"key":"9557_CR2","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E.: An nlogn algorithm for minimizing states in a finite automaton. Technical report, Stanford, CA, USA (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"9557_CR3","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 Inform. 2, 97\u2013109 (1973)","journal-title":"Acta Inform."},{"issue":"1\u20132","key":"9557_CR4","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 250(1\u20132), 333\u2013363 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"30\u201332","key":"9557_CR5","doi-asserted-by":"crossref","first-page":"2811","DOI":"10.1016\/j.tcs.2009.01.039","volume":"410","author":"J. Berstel","year":"2009","unstructured":"Berstel, J., Boasson, L., Carton, O.: Continuant polynomials and worst-case behavior of Hopcroft\u2019s minimization algorithm. Theor. Comput. Sci. 410(30\u201332), 2811\u20132822 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9557_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/978-3-540-88282-4_17","volume-title":"Second International Conference on Language and Automata Theory and Applications (LATA 2008)","author":"G. Castiglione","year":"2008","unstructured":"Castiglione, G., Restivo, A., Sciortino, M.: Hopcroft\u2019s algorithm and cyclic automata. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) Second International Conference on Language and Automata Theory and Applications (LATA 2008). Lecture Notes in Computer Science, vol. 5196, pp. 172\u2013183. Springer, Berlin (2008)"},{"issue":"38\u201339","key":"9557_CR7","doi-asserted-by":"crossref","first-page":"3414","DOI":"10.1016\/j.tcs.2010.05.025","volume":"411","author":"G. Castiglione","year":"2010","unstructured":"Castiglione, G., Restivo, A., Sciortino, M.: On extremal cases of Hopcroft\u2019s algorithm. Theor. Comput. Sci. 411(38\u201339), 3414\u20133422 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9557_CR8","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0020-0190(95)00199-9","volume":"57","author":"N. Blum","year":"1996","unstructured":"Blum, N.: An ${\\mathcal{O}}(n \\log n)$ implementation of the standard method for minimizing n-state finite automata. Inf. Process. Lett. 57(2), 65\u201369 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9557_CR9","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107341005","volume-title":"Applied Combinatorics on Words","author":"M. Lothaire","year":"2005","unstructured":"Lothaire, M.: Applied Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol.\u00a0105. Cambridge University Press, Cambridge (2005)"},{"key":"9557_CR10","series-title":"Dagstuhl Seminar Proceedings","first-page":"645","volume-title":"25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008),Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI)","author":"A. Valmari","year":"2008","unstructured":"Valmari, A., Lehtinen, P.: Efficient minimization of DFAs with partial transition functions. In: Albers, S., Weil, P. (eds.) 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008),Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol.\u00a008001, pp. 645\u2013656 (2008)"},{"key":"9557_CR11","first-page":"9","volume-title":"Seventh International Workshop on Finite-State Methods and Natural Language Processing (FSMNLP\u201908)","author":"M.P. Beal","year":"2008","unstructured":"Beal, M.P., Crochemore, M.: Minimizing incomplete automata. In: Seventh International Workshop on Finite-State Methods and Natural Language Processing (FSMNLP\u201908), pp. 9\u201316 (2008)"},{"key":"9557_CR12","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)"},{"key":"9557_CR13","first-page":"529","volume-title":"Symposium on the Mathematical Theory of Automata. Polytechnic Institute of Brooklyn","author":"J.A. Brzozowski","year":"1962","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Symposium on the Mathematical Theory of Automata. Polytechnic Institute of Brooklyn, vol. 12, pp. 529\u2013561. Polytechnic Press, New York (1962)"},{"key":"9557_CR14","first-page":"96","volume-title":"The Prague Stringology Conference\u201902","author":"J.M. Champarnaud","year":"2002","unstructured":"Champarnaud, J.M., Khorsi, A., Paranthoen, T.: Split and join for minimizing: Brzozowski\u2019s algorithm. In: The Prague Stringology Conference\u201902, pp. 96\u2013104 (2002)"},{"key":"9557_CR15","unstructured":"Watson, B.W.: A taxonomy of finite automata minimization algorithms. Technical Report of Faculty of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands (1994)"},{"issue":"1","key":"9557_CR16","doi-asserted-by":"crossref","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. 92(1), 181\u2013189 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"9557_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/3-540-48340-3_21","volume-title":"24th International Symposium on Mathematical Foundations of Computer Science 1999 (MFCS\u201999)","author":"C. Nicaud","year":"1999","unstructured":"Nicaud, C.: Average state complexity of operations on unary automata. In: Kutylowski, M., Pacholski, L., Wierzbicki, T. (eds.) 24th International Symposium on Mathematical Foundations of Computer Science 1999 (MFCS\u201999). Lecture Notes in Computer Science, vol. 1672, pp. 231\u2013240. Springer, Berlin (1999)"},{"key":"9557_CR18","doi-asserted-by":"crossref","first-page":"1376","DOI":"10.1109\/ISIT.2007.4557131","volume-title":"IEEE International Symposium on Information Theory (ISIT\u201907)","author":"M.P. Beal","year":"2007","unstructured":"Beal, M.P., Crochemore, M.: Minimizing local automata. In: Caire, G., Fossorier, M. (eds.): IEEE International Symposium on Information Theory (ISIT\u201907), pp. 1376\u20131380 (2007)"},{"key":"9557_CR19","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2007.04.001","volume":"381","author":"F. Bassino","year":"2007","unstructured":"Bassino, F., Nicaud, C.: Enumeration and random generation of accessible automata. Theor. Comput. Sci. 381, 86\u2013104 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9557_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/978-3-540-76336-9_28","volume-title":"12th International Conference Implementation and Application of Automata (CIAA 2007)","author":"F. Bassino","year":"2007","unstructured":"Bassino, F., David, J., Nicaud, C.: REGAL: a library to randomly and exhaustively generate automata. In: 12th International Conference Implementation and Application of Automata (CIAA 2007). Lecture Notes in Computer Science, vol. 4783, pp. 303\u2013305 (2007)"},{"key":"9557_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/cpa.3160190102","volume":"19","author":"F. Bassino","year":"2010","unstructured":"Bassino, F., David, J., Nicaud, C.: Enumeration and random generation of possibly incomplete deterministic automata. Pure Math. Appl. 19, 1\u201316 (2010)","journal-title":"Pure Math. Appl."},{"key":"9557_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/978-3-642-15155-2_29","volume-title":"35th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201910)","author":"J. David","year":"2010","unstructured":"David, J.: The average complexity of Moore\u2019s state minimization algorithm is ${\\mathcal{O}}(n\\log\\log n)$ . In: Hlinen\u00fd, P., Kucera, A. (eds.) 35th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201910). Lecture Notes in Computer Science, vol. 6281, pp. 318\u2013329. Springer, Berlin (2010)"},{"key":"9557_CR23","series-title":"Dagstuhl Seminar Proceedings","first-page":"123","volume-title":"26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2009), Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Germany Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI)","author":"F. Bassino","year":"2009","unstructured":"Bassino, F., David, J., Nicaud, C.: On the average complexity of Moore\u2019s state minimization algorithm. In: Albers, S., Marion, J.Y. (eds.) 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2009), Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Germany Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany. Dagstuhl Seminar Proceedings, vol. 09001, pp.\u00a0123\u2013134 (2009)"},{"key":"9557_CR24","first-page":"541","volume-title":"Proc. American Mathematical Society","author":"A. Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformation. In: Proc. American Mathematical Society, pp. 541\u2013544 (1958)"},{"issue":"9","key":"9557_CR25","first-page":"459","volume":"22","author":"A.D. Korshunov","year":"1986","unstructured":"Korshunov, A.D.: On the number of non-isomorphic strongly connected finite automata. Elektron. Inf.verarb. Kybern. 22(9), 459\u2013462 (1986)","journal-title":"Elektron. Inf.verarb. Kybern."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9557-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9557-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9557-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T09:51:50Z","timestamp":1560765110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9557-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,12]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9557"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9557-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2011,10,12]]}}}