{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:06:26Z","timestamp":1767236786943,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662445211"},{"type":"electronic","value":"9783662445228"}],"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-662-44522-8_2","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:12:23Z","timestamp":1407838343000},"page":"5-23","source":"Crossref","is-referenced-by-count":9,"title":["Random Deterministic Automata"],"prefix":"10.1007","author":[{"given":"Cyril","family":"Nicaud","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-02979-0_10","volume-title":"Implementation and Application of Automata","author":"A. Almeida","year":"2009","unstructured":"Almeida, A., Almeida, M., Alves, J., Moreira, N., Reis, R.: Fado and guitar. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol.\u00a05642, pp. 65\u201374. Springer, Heidelberg (2009)"},{"issue":"2","key":"2_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2007.07.029","volume":"387","author":"M. Almeida","year":"2007","unstructured":"Almeida, M., Moreira, N., Reis, R.: Enumeration and generation with a string automata representation. Theor. Comput. Sci.\u00a0387(2), 93\u2013102 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-76336-9_28","volume-title":"Implementation and Application of Automata","author":"F. Bassino","year":"2007","unstructured":"Bassino, F., David, J., Nicaud, C.: REGAL: A library to randomly and exhaustively generate automata. In: Holub, J., \u017d\u010f\u00e1rek, J. (eds.) CIAA 2007. LNCS, vol.\u00a04783, pp. 303\u2013305. Springer, Heidelberg (2007)"},{"key":"2_CR4","series-title":"LIPIcs","first-page":"123","volume-title":"STACS 2009","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.) STACS 2009. LIPIcs, vol.\u00a03, pp. 123\u2013134. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"issue":"1-2","key":"2_CR5","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":"2_CR6","unstructured":"Bassino, F., David, J., Sportiello, A.: Asymptotic enumeration of minimal automata. In: D\u00fcrr, C., Wilke, T. (eds.) STACS 2012. LIPIcs, vol.\u00a014, pp. 88\u201399. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"issue":"1-3","key":"2_CR7","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":"2_CR8","unstructured":"Bassino, F., Sportiello, A.: Linear-time generation of specifiable combinatorial structures: General theory and first examples. arXiv, abs\/1307.1728 (2013)"},{"key":"2_CR9","unstructured":"Berend, D., Kontorovich, A.: The state complexity of random DFAs. arXiv, abs\/1307.0720 (2013)"},{"key":"2_CR10","unstructured":"Berlinkov, M.V.: On the probability to be synchronizable. arXiv, abs\/1304.5774 (2013)"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511814068"},{"key":"2_CR12","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, Polyt. Instit. of Brooklyn, N.Y. (1962)"},{"key":"2_CR13","unstructured":"Carayol, A., Nicaud, C.: Distribution of the number of accessible states in a random deterministic automaton. In: D\u00fcrr, C., Wilke, T. (eds.) STACS 2012. LIPIcs, vol.\u00a014, pp. 194\u2013205. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"2_CR14","unstructured":"\u010cern\u00fd, J.: Pozn\u00e1mka k. homog\u00e9nnym experimentom s konecnymi automatmi. Matematicko-fyzikalny \u010casopis Slovensk, 14 (1964)"},{"key":"2_CR15","unstructured":"Champarnaud, J.-M., Khorsi, A., Parantho\u00ebn, T.: Split and join for minimizing: Brzozowski\u2019s algorithm. In: Bal\u00edk, M., Sim\u00e1nek, M. (eds.) Stringology 2002, pp. 96\u2013104 (2002)"},{"issue":"2","key":"2_CR16","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.tcs.2004.03.072","volume":"330","author":"J.-M. Champarnaud","year":"2005","unstructured":"Champarnaud, J.-M., Parantho\u00ebn, T.: Random generation of DFAs. Theor. Comput. Sci.\u00a0330(2), 221\u2013235 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR17","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press (1994)"},{"key":"2_CR18","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":"2_CR19","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. De Felice","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":"2_CR20","doi-asserted-by":"crossref","unstructured":"De Felice, S., Nicaud, C.: On the average complexity of Brzozowski\u2019s algorithm for deterministic automata with a small number of final states. In: DLT 2014 (to appear in LNCS, 2014)","DOI":"10.1007\/978-3-319-09698-8_3"},{"issue":"2","key":"2_CR21","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(98)00323-5","volume":"218","author":"A. Denise","year":"1999","unstructured":"Denise, A., Zimmermann, P.: Uniform random generation of decomposable structures using floating-point arithmetic. Theor. Comput. Sci.\u00a0218(2), 233\u2013248 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"4-5","key":"2_CR22","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1017\/S0963548304006315","volume":"13","author":"P. Duchon","year":"2004","unstructured":"Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures. Comb. Prob. Comp.\u00a013(4-5), 577\u2013625 (2004)","journal-title":"Comb. Prob. Comp."},{"key":"2_CR23","unstructured":"Feller, W.: An Introduction to Probability Theory and its Applications, vol.\u00a01. Wiley (1968)"},{"key":"2_CR24","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":"2_CR25","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511801655"},{"issue":"2","key":"2_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)90226-7","volume":"132","author":"P. Flajolet","year":"1994","unstructured":"Flajolet, P., Zimmermann, P., Van Cutsem, B.: A calculus for the random generation of labelled combinatorial structures. Theor. Comput. Sci.\u00a0132(2), 1\u201335 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1214\/aoms\/1177705156","volume":"32","author":"I.J. Good","year":"1961","unstructured":"Good, I.J.: An asymptotic formula for the differences of the powers at zero. Ann. Math. Statist.\u00a032, 249\u2013256 (1961)","journal-title":"Ann. Math. Statist."},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"100","DOI":"10.4153\/CJM-1965-010-9","volume":"17","author":"M. Harrison","year":"1965","unstructured":"Harrison, M.: A census of finite automata. Canadian J. Math.\u00a017, 100\u2013113 (1965)","journal-title":"Canadian J. Math."},{"key":"2_CR29","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":"2_CR30","series-title":"Addison-Wesley Series in Computer Science","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 Series in Computer Science. Addison-Wesley Publishing Co., Reading (1979)"},{"issue":"1","key":"2_CR31","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/rsa.3240010106","volume":"1","author":"R.M. Karp","year":"1990","unstructured":"Karp, R.M.: The transitive closure of a random digraph. Random Struct. Algorithms\u00a01(1), 73\u201394 (1990)","journal-title":"Random Struct. Algorithms"},{"key":"2_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-38768-5_18","volume-title":"Computing and Combinatorics","author":"A. Kisielewicz","year":"2013","unstructured":"Kisielewicz, A., Kowalski, J., Szyku\u0142a, M.: A fast algorithm finding the shortest reset words. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol.\u00a07936, pp. 182\u2013196. Springer, Heidelberg (2013)"},{"key":"2_CR33","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume I: Fundamental Algorithms, 3rd edn. Addison-Wesley (1997)"},{"key":"2_CR34","unstructured":"Kol\u010din, V.: Random Mappings: Translation Series in Mathematics and Engineering. Translations series in mathematics and engineering. Springer London, Limited (1986)"},{"key":"2_CR35","unstructured":"Korshunov, A.: Enumeration of finite automata. Problemy Kibernetiki\u00a034, 5\u201382 (1978) (in Russian)"},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"Lebensztayn, E.: On the asymptotic enumeration of accessible automata. DMTCS\u00a012(3) (2010)","DOI":"10.46298\/dmtcs.512"},{"key":"#cr-split#-2_CR37.1","doi-asserted-by":"crossref","unstructured":"Liskovets, V.A.: The number of initially connected automata. Cybernetics\u00a04, 259-262 (1969)","DOI":"10.1007\/BF01070908"},{"key":"#cr-split#-2_CR37.2","unstructured":"English translation of Kibernetika (3), 16-19 (1969)"},{"issue":"1-2","key":"2_CR38","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.tcs.2004.07.007","volume":"328","author":"S. Lombardy","year":"2004","unstructured":"Lombardy, S., R\u00e9gis-Gianas, Y., Sakarovitch, J.: Introducing VAUCANSON. Theor. Comput. Sci.\u00a0328(1-2), 77\u201396 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Moore, E.F.: Gedanken experiments on sequential machines. In: Automata Studies, pp. 129\u2013153. Princeton U. (1956)","DOI":"10.1515\/9781400882618-006"},{"key":"2_CR40","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: Kuty\u0142owski, M., Wierzbicki, T., Pacholski, L. (eds.) MFCS 1999. LNCS, vol.\u00a01672, pp. 231\u2013240. Springer, Heidelberg (1999)"},{"key":"2_CR41","unstructured":"Nicaud, C.: Comportement en moyenne des automates finis et des langages rationnels. PhD Thesis, Universit\u00e9 Paris VII (2000) (in French)"},{"key":"2_CR42","unstructured":"Nicaud, C.: Fast synchronization of random automata. arXiv, abs\/1404.6962 (2014)"},{"key":"2_CR43","unstructured":"Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms. Academic Press (1978)"},{"key":"2_CR44","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","Mathematical Foundations of Computer Science 2014"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44522-8_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T01:52:36Z","timestamp":1675821156000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-44522-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662445211","9783662445228"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44522-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}