{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:34:36Z","timestamp":1725798876503},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319096971"},{"type":"electronic","value":"9783319096988"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09698-8_3","type":"book-chapter","created":{"date-parts":[[2014,8,18]],"date-time":"2014-08-18T00:52:51Z","timestamp":1408323171000},"page":"25-36","source":"Crossref","is-referenced-by-count":1,"title":["On the Average Complexity of Brzozowski\u2019s Algorithm for Deterministic Automata with a Small Number of Final States"],"prefix":"10.1007","author":[{"given":"Sven","family":"De Felice","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Nicaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"3_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: An aid to bibliographic search. Commun. ACM\u00a018(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"issue":"1-2","key":"3_CR2","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":"3_CR3","unstructured":"Bassino, F., David, J., Sportiello, A.: Asymptotic enumeration of minimal automata. In: D\u00fcrr, Wilke (eds.) [8], pp. 88\u201399"},{"key":"3_CR4","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":"3_CR5","unstructured":"Carayol, A., Nicaud, C.: Distribution of the number of accessible states in a random deterministic automaton. In: D\u00fcrr, Wilke (eds.) [8], pp. 194\u2013205"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Chassaing, P., Marckert, J.F.: Parking functions, empirical processes, and the width of rooted labeled trees. Electron. J. Combin.\u00a08(1) (2001)","DOI":"10.37236\/1558"},{"key":"3_CR7","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":"3_CR8","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)"},{"issue":"3-4","key":"3_CR9","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF02280290","volume":"18","author":"P. Erdos","year":"1967","unstructured":"Erdos, P., Tur\u00e1n, P.: On some problems of a statistical group theory, III. Acta Math. Acad. Sci. Hungar.\u00a018(3-4), 309\u2013320 (1967)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-642-38771-5_17","volume-title":"Developments in Language Theory","author":"S. Felice De","year":"2013","unstructured":"De Felice, S., Nicaud, C.: Brzozowski algorithm is generically super-polynomial for deterministic automata. In: B\u00e9al, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol.\u00a07907, pp. 179\u2013190. Springer, Heidelberg (2013)"},{"key":"3_CR11","doi-asserted-by":"crossref","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)","DOI":"10.1007\/3-540-46885-4_34"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511801655"},{"key":"3_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":"3_CR14","unstructured":"Kol\u010din, V.: Random Mappings: Translation Series in Mathematics and Engineering. Translations series in mathematics and engineering. Springer London, Limited (1986), http:\/\/books.google.fr\/books?id=roOiPwAACAAJ"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09698-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,23]],"date-time":"2020-08-23T12:01:29Z","timestamp":1598184089000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09698-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319096971","9783319096988"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09698-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}