{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:21Z","timestamp":1759638561990},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387708"},{"type":"electronic","value":"9783642387715"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38771-5_17","type":"book-chapter","created":{"date-parts":[[2013,6,10]],"date-time":"2013-06-10T02:16:25Z","timestamp":1370830585000},"page":"179-190","source":"Crossref","is-referenced-by-count":3,"title":["Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata"],"prefix":"10.1007","author":[{"given":"Sven","family":"De Felice","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Nicaud","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"17_CR1","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00453-011-9557-7","volume":"63","author":"F. Bassino","year":"2012","unstructured":"Bassino, F., David, J., Nicaud, C.: Average case analysis of Moore\u2019s state minimization algorithm. Algorithmica\u00a063(1-2), 509\u2013531 (2012)","journal-title":"Algorithmica"},{"key":"17_CR2","unstructured":"Bassino, F., David, J., Sportiello, A.: Asymptotic enumeration of minimal automata. In: D\u00fcrr, Wilke (eds.) [9], pp. 88\u201399"},{"issue":"4","key":"17_CR3","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1142\/S0129054110007398","volume":"21","author":"F. Bassino","year":"2010","unstructured":"Bassino, F., Giambruno, L., Nicaud, C.: The average state complexity of rational operations on finite languages. International Journal of Foundations of Computer Science\u00a021(4), 495\u2013516 (2010)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1-3","key":"17_CR4","doi-asserted-by":"publisher","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.\u00a0381(1-3), 86\u2013104 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR5","series-title":"MRI Symposia Series","first-page":"529","volume-title":"Mathematical Theory of Automata","author":"J.A. Brzozowski","year":"1962","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Mathematical Theory of Automata. MRI Symposia Series, vol.\u00a012, pp. 529\u2013561. Polytechnic Press, Polytechnic Institute of Brooklyn, N.Y (1962)"},{"key":"17_CR6","unstructured":"Carayol, A., Nicaud, C.: Distribution of the number of accessible states in a random deterministic automaton. In: D\u00fcrr, Wilke (eds.) [9], pp. 194\u2013205"},{"key":"17_CR7","unstructured":"Chassaing, P., Azad, E.Z.: Asymptotic behavior of some factorizations of random words (2010), arXiv:1004.4062v1"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.tcs.2011.10.011","volume":"417","author":"J. David","year":"2012","unstructured":"David, J.: Average complexity of Moore\u2019s and Hopcroft\u2019s algorithms. Theor. Comput. Sci.\u00a0417, 50\u201365 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR9","unstructured":"D\u00fcrr, C., Wilke, T. (eds.): 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, February 29 - March 3. LIPIcs, vol.\u00a014. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF00536750","volume":"4","author":"P. Erd\u0151s","year":"1965","unstructured":"Erd\u0151s, P., Tur\u00e1n, P.: On some problems of a statistical group-theory I. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete\u00a04, 175\u2013186 (1965)","journal-title":"Z. Wahrscheinlichkeitstheorie und Verw. Gebiete"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/3-540-46885-4_34","volume-title":"Advances in Cryptology - EUROCRYPT \u201989","author":"P. Flajolet","year":"1990","unstructured":"Flajolet, P., Odlyzko, A.M.: Random mapping statistics. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol.\u00a0434, pp. 329\u2013354. Springer, Heidelberg (1990)"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511801655"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E.: An n logn algorithm for minimizing the states in a finite automaton. In: Kohavi, Z. (ed.) The Theory of Machines and Computations, pp. 189\u2013196. Academic Press (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"17_CR14","first-page":"5","volume":"34","author":"A. Korshunov","year":"1978","unstructured":"Korshunov, A.: Enumeration of finite automata. Problemy Kibernetiki\u00a034, 5\u201382 (1978) (in Russian)","journal-title":"Problemy Kibernetiki"},{"key":"17_CR15","unstructured":"Landau, E.: Handbuch der lehre von der verteilung der primzahlen, vol.\u00a02. B. G. Teubner (1909)"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/3-540-48340-3_21","volume-title":"Mathematical Foundations of Computer Science 1999","author":"C. Nicaud","year":"1999","unstructured":"Nicaud, C.: Average state complexity of operations on unary automata. In: Kutylowski, M., Pacholski, L., Wierzbicki, T. (eds.) MFCS 1999. LNCS, vol.\u00a01672, pp. 231\u2013240. Springer, Heidelberg (1999)"},{"key":"17_CR17","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11591191_28","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Tabakov","year":"2005","unstructured":"Tabakov, D., Vardi, M.Y.: Experimental evaluation of classical automata constructions. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS (LNAI), vol.\u00a03835, pp. 396\u2013411. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38771-5_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T00:29:44Z","timestamp":1557793784000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38771-5_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387708","9783642387715"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38771-5_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}