{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T19:16:07Z","timestamp":1773083767050,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540310235","type":"print"},{"value":"9783540330974","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11605157_2","type":"book-chapter","created":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T10:07:40Z","timestamp":1141207660000},"page":"15-30","source":"Crossref","is-referenced-by-count":11,"title":["The Language, the Expression, and the (Small) Automaton"],"prefix":"10.1007","author":[{"given":"Jacques","family":"Sakarovitch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"Automata, Languages, and Machines","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol.\u00a0A. Academic Press, London (1974)"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and Context-free Languages. B. G. Teubner (1979)","DOI":"10.1007\/978-3-663-09367-1"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/TEC.1960.5221603","volume":"9","author":"R. McNaughton","year":"1960","unstructured":"McNaughton, R., Yamada, H.: Regular expressions and state graphs for automata. IRE Trans. Electronic Computers\u00a09, 39\u201347 (1960)","journal-title":"IRE Trans. Electronic Computers"},{"key":"2_CR4","volume-title":"Theory of Computation","author":"D. Wood","year":"1987","unstructured":"Wood, D.: Theory of Computation. John Wiley, Chichester (1987)"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a01, pp. 41\u2013111. Elsevier, Amsterdam (1997)"},{"key":"2_CR6","volume-title":"Regular Algebra and Finite Machines","author":"J.H. Conway","year":"1971","unstructured":"Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, Boca Raton (1971)"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0304-3975(91)90395-I","volume":"89","author":"D. Krob","year":"1991","unstructured":"Krob, D.: Complete systems of B-rational identities. Theoret. Computer Sci.\u00a089, 207\u2013343 (1991)","journal-title":"Theoret. Computer Sci."},{"key":"2_CR8","unstructured":"Sakarovitch, J.: El\u00e9ments de th\u00e9orie des automates. Vuibert, English translation: Elements of Automata Theory, Cambridge University Press, Cambridge (to appear, 2003)"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/PGEC.1963.263416","volume":"12","author":"J.A. Brzozowski","year":"1963","unstructured":"Brzozowski, J.A., McCluskey, E.J.: Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. Electronic Computers\u00a012, 67\u201376 (1963)","journal-title":"IEEE Trans. Electronic Computers"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"67","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. CIAA 2003\u00a0328, 67\u201376 (2004); Journal version of Proc. of CIAA 2003, Lect. Notes in Comp. Sc. 2759, pp. 96\u2013107 (2003) (with R. Poss)","journal-title":"Theoret. Computer Sci."},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-540-30500-2_31","volume-title":"Implementation and Application of Automata","author":"M. Delgado","year":"2005","unstructured":"Delgado, M.: Approximation to the smallest regular expression for a given regular language. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 312\u2013314. Springer, Heidelberg (2005)"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/11605157_10","volume-title":"Implementation and Application of Automata","author":"T. Claveirole","year":"2006","unstructured":"Claveirole, T., Lombardy, S., O\u2019Connor, S., Pouchet, L.-N., Sakarovitch, J.: Inside vaucanson. In: Farr\u00e9, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol.\u00a03845, pp. 116\u2013128. Springer, Heidelberg (2006)"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","volume":"16","author":"V.M. Glushkov","year":"1961","unstructured":"Glushkov, V.M.: The abstract theory of automata. Russian Math. Surveys\u00a016, 1\u201353 (1961)","journal-title":"Russian Math. Surveys"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-44674-5_5","volume-title":"Implementation and Application of Automata","author":"P. Caron","year":"2001","unstructured":"Caron, P., Flouret, M.: Glushkov construction for multiplicities. In: Yu, S., P\u0103un, A. (eds.) CIAA 2000. LNCS, vol.\u00a02088, pp. 52\u201361. Springer, Heidelberg (2001)"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.tcs.2004.10.016","volume":"332","author":"S. Lombardy","year":"2005","unstructured":"Lombardy, S., Sakarovitch, J.: Derivatives of rational expressions with multiplicity. Theor. Comput. Sci.\u00a0332, 141\u2013177 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR16","first-page":"419","volume":"11","author":"K. Thompson","year":"1968","unstructured":"Thompson, K.: Regular expression search algorithm. Comm. Assoc. Comput. Mach.\u00a011, 419\u2013422 (1968)","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J.A. Brzozowski","year":"1964","unstructured":"Brzozowski, J.A.: Derivatives of regular expressions. J. Assoc. Comput. Mach.\u00a011, 481\u2013494 (1964)","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"V. Antimirov","year":"1996","unstructured":"Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci.\u00a0155, 291\u2013319 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0304-3975(86)90088-5","volume":"48","author":"G. Berry","year":"1986","unstructured":"Berry, G., Sethi, R.: From regular expressions to deterministic automata. Theor. Comput. Sci.\u00a048, 117\u2013126 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/0304-3975(95)00104-2","volume":"155","author":"J. Berstel","year":"1996","unstructured":"Berstel, J., Pin, J.E.: Local languages and the Berry-Sethi algorithm. Theor. Comput. Sci.\u00a0155, 439\u2013446 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0304-3975(01)00267-5","volume":"289","author":"J.M. Champarnaud","year":"2002","unstructured":"Champarnaud, J.M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci.\u00a0289, 137\u2013163 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"120","author":"A. Br\u00fcgemann-Klein","year":"1993","unstructured":"Br\u00fcgemann-Klein, A.: Regular expressions into finite automata. Theor. Comput. Sci.\u00a0120, 197\u2013213 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita:2000116","volume":"34","author":"C. Hagenah","year":"2000","unstructured":"Hagenah, C., Musholl, A.: Computing \u03b5-free NFAs from regular expressions in O(nlog2(n)) time. Theoret. Inform. Appl.\u00a034, 257\u2013277 (2000)","journal-title":"Theoret. Inform. Appl."},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1006\/jcss.2001.1748","volume":"62","author":"J. Hromkovic","year":"2001","unstructured":"Hromkovic, J., Seibert, S., Wilke, T.: Translating regular expressions into small \u03b5-free nondeterministic finite automata. J. Comput. System Sci.\u00a062, 565\u2013588 (2001)","journal-title":"J. Comput. System Sci."},{"key":"2_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-45452-7_23","volume-title":"Combinatorial Pattern Matching","author":"L. Ilie","year":"2002","unstructured":"Ilie, L., Yu, S.: Constructing NFAs by optimal use of positions in regular expressions. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 279\u2013288. Springer, Heidelberg (2002)"},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-540-30500-2_9","volume-title":"Implementation and Application of Automata","author":"J.M. Champarnaud","year":"2005","unstructured":"Champarnaud, J.M., Nicart, F., Ziadi, D.: Computing the follow automaton of an expression. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 90\u2013101. Springer, Heidelberg (2005)"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0304-3975(97)00296-X","volume":"233","author":"P. Caron","year":"2000","unstructured":"Caron, P., Ziadi, D.: Characterization of Glushkov automata. Theor. Comput. Sci.\u00a0233, 75\u201390 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1051\/ita:2005013","volume":"39","author":"S. Lombardy","year":"2005","unstructured":"Lombardy, S., Sakarovitch, J.: How expressions can code for automata. Theoret. Inform. App.\u00a039, 217\u2013237 (2005)","journal-title":"Theoret. Inform. App."}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11605157_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:05:16Z","timestamp":1619492716000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11605157_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540310235","9783540330974"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11605157_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}