{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:05Z","timestamp":1725745265908},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642405785"},{"type":"electronic","value":"9783642405792"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40579-2_6","type":"book-chapter","created":{"date-parts":[[2013,8,14]],"date-time":"2013-08-14T10:24:48Z","timestamp":1376475888000},"page":"18-33","source":"Crossref","is-referenced-by-count":0,"title":["Words, Trees and Automata Minimization"],"prefix":"10.1007","author":[{"given":"Giusi","family":"Castiglione","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-31653-1_6","volume-title":"Developments in Language Theory","author":"J.A. Brzozowski","year":"2012","unstructured":"Brzozowski, J.A., Tamm, H.: Quotient complexities of atoms of regular languages. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol.\u00a07410, pp. 50\u201361. Springer, Heidelberg (2012)"},{"key":"6_CR2","unstructured":"Brzozowski, J.A., Tamm, H.: Minimal nondeterministic finite automata and atoms of regular languages. CoRR, abs\/1301.5585 (2013)"},{"key":"6_CR3","unstructured":"Almeida, M., Moreira, N., Reis, R.: On the performance of automata minimization algorithms. Technical Report DCC-2007-03, Universidade do Porto (2007)"},{"key":"6_CR4","doi-asserted-by":"publisher","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.\u00a0410, 2811\u20132822 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"6_CR5","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s00224-009-9228-0","volume":"46","author":"J. Berstel","year":"2010","unstructured":"Berstel, J., Boasson, L., Carton, O., Fagnot, I.: Sturmian trees. Theory of Computing Systems\u00a046(3), 443\u2013478 (2010)","journal-title":"Theory of Computing Systems"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"6_CR7","first-page":"529","volume":"12","author":"J.A. Brzozowski","year":"1962","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata\u00a012, 529\u2013561 (1962)","journal-title":"Mathematical Theory of Automata"},{"key":"6_CR8","unstructured":"Castiglione, C., Sciortino, M.: Moore automata and epichristoffel words. In: ICTCS 2012 - 13th Italian Conference on Theoretical Computer Science (2012)"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-642-18098-9_27","volume-title":"Implementation and Application of Automata","author":"G. Castiglione","year":"2011","unstructured":"Castiglione, G., Nicaud, C., Sciortino, M.: A challenging family of automata for classical minimization algorithms. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol.\u00a06482, pp. 251\u2013260. Springer, Heidelberg (2011)"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-540-88282-4_17","volume-title":"Language and Automata Theory and Applications","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.) LATA 2008. LNCS, vol.\u00a05196, pp. 172\u2013183. Springer, Heidelberg (2008)"},{"issue":"43","key":"6_CR11","doi-asserted-by":"publisher","first-page":"4372","DOI":"10.1016\/j.tcs.2009.07.018","volume":"410","author":"G. Castiglione","year":"2009","unstructured":"Castiglione, G., Restivo, A., Sciortino, M.: Circular sturmian words and Hopcroft\u2019s algorithm. Theor. Comput. Sci.\u00a0410(43), 4372\u20134381 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"38-39","key":"6_CR12","doi-asserted-by":"publisher","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.\u00a0411(38-39), 3414\u20133422 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1051\/ita\/2011011","volume":"45","author":"G. Castiglione","year":"2011","unstructured":"Castiglione, G., Restivo, A., Sciortino, M.: Hopcroft\u2019s algorithm and tree-like automata. RAIRO - Theor. Inf. and Applic.\u00a045(1), 59\u201375 (2011)","journal-title":"RAIRO - Theor. Inf. and Applic."},{"key":"6_CR14","unstructured":"Champarnaud, J.-M., Khorsi, A., Parantho\u00ebn, T.: Split and join for minimizing: Brzozowski\u2019s algorithm. In: PSC 2002, pp. 96\u2013104 (2002)"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/3-540-63246-8_15","volume-title":"Structures in Logic and Computer Science","author":"A. Luca de","year":"1997","unstructured":"de Luca, A.: Combinatories of standard sturmian words. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol.\u00a01261, pp. 249\u2013267. Springer, Heidelberg (1997)"},{"issue":"2","key":"6_CR16","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)00035-H","volume":"136","author":"A. Luca de","year":"1994","unstructured":"de Luca, A., Mignosi, F.: Some combinatorial properties of sturmian words. Theor. Comput. Sci.\u00a0136(2), 361\u2013385 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.tcs.2012.03.012","volume":"454","author":"F. Mignosi","year":"2012","unstructured":"Mignosi, F., Restivo, A.: Characteristic sturmian words are extremal for the critical factorization theorem. Theor. Comput. Sci.\u00a0454, 199\u2013205 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"38-40","key":"6_CR18","doi-asserted-by":"publisher","first-page":"3782","DOI":"10.1016\/j.tcs.2009.05.014","volume":"410","author":"G. Paquin","year":"2009","unstructured":"Paquin, G.: On a generalization of christoffel words: epichristoffel words. Theor. Comput. Sci.\u00a0410(38-40), 3782\u20133791 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR19","unstructured":"Garc\u00eda, P., L\u00f3pez, D., V\u00e1zquez de Parga, M.: DFA minimization: from Brzozowski to Hopcroft. Technical report, Universidad Polit\u00e9cnica de Valencia. Informes t\u00e9cnicos de investigaci\u00f3n DSIC-TLCC (2013), http:\/\/hdl.handle.net\/10251\/27623"},{"key":"6_CR20","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: Theory of Machines and Computations (Proc. Internat. Sympos. Technion, Haifa, 1971), pp. 189\u2013196. Academic Press, New York (1971)"},{"key":"6_CR21","unstructured":"Berstel, J., Boasson, L., Carton, O., Fagnot, I.: Minimization of automata. CoRR, abs\/1010.5318 (2010)"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-540-73208-2_36","volume-title":"Developments in Language Theory","author":"M. Sciortino","year":"2007","unstructured":"Sciortino, M., Zamboni, L.Q.: Suffix automata and standard sturmian words. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 382\u2013398. Springer, Heidelberg (2007)"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.tcs.2013.03.005","volume":"487","author":"M. Vazquez de Parga","year":"2013","unstructured":"Vazquez de Parga, M., Garcia, P., Lopez, D.: A polynomial double reversal minimization algorithm for deterministic finite automata. Theor. Comput. Sci.\u00a0487, 17\u201322 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Moore, E.F.: Gedaken experiments on sequential machines, pp. 129\u2013153. Princeton University Press (1956)","DOI":"10.1515\/9781400882618-006"},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0304-3975(85)90159-8","volume":"40","author":"R. Paige","year":"1985","unstructured":"Paige, R., Tarjan, R.E., Bonic, R.: A linear time solution to the single function coarsest partition problem. Theor. Comput. Sci.\u00a040, 67\u201384 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR26","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)"},{"issue":"5","key":"6_CR27","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0020-0190(02)00512-4","volume":"86","author":"S. Mantaci","year":"2003","unstructured":"Mantaci, S., Restivo, A., Sciortino, M.: Burrows-Wheeler transform and sturmian words. Inf. Process. Lett.\u00a086(5), 241\u2013246 (2003)","journal-title":"Inf. Process. Lett."},{"key":"6_CR28","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","Combinatorics on Words"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40579-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T23:44:24Z","timestamp":1563666264000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40579-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642405785","9783642405792"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40579-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}