{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T21:58:02Z","timestamp":1768687082910,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642223204","type":"print"},{"value":"9783642223211","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22321-1_9","type":"book-chapter","created":{"date-parts":[[2011,7,15]],"date-time":"2011-07-15T03:58:48Z","timestamp":1310702328000},"page":"93-104","source":"Crossref","is-referenced-by-count":4,"title":["The Average Transition Complexity of Glushkov and Partial Derivative Automata"],"prefix":"10.1007","author":[{"given":"Sabine","family":"Broda","sequence":"first","affiliation":[]},{"given":"Ant\u00f3nio","family":"Machiavelo","sequence":"additional","affiliation":[]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"9_CR1","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"V.M. Antimirov","year":"1996","unstructured":"Antimirov, V.M.: Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci.\u00a0155(2), 291\u2013319 (1996)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"48","author":"A. Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A.: Regular expressions into finite automata. Theoret. Comput. Sci.\u00a048, 197\u2013213 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average size of Glushkov and partial derivative automata. Technical Report DCC-2011-03, FCUP & CMUP, Universidade do Porto (April 2011)","DOI":"10.1007\/978-3-642-22321-1_9"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average state complexity of partial derivative automata. International Journal of Foundations of Computer Science (2011) (accepted to publication)","DOI":"10.1007\/978-3-642-22321-1_9"},{"issue":"4","key":"9_CR5","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. JACM\u00a011(4), 481\u2013494 (1964)","journal-title":"JACM"},{"key":"9_CR6","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. Theoret. Comput. Sci.\u00a048, 117\u2013126 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"1-2","key":"9_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(96)00140-5","volume":"178","author":"C.-H. Chang","year":"1997","unstructured":"Chang, C.-H., Paige, R.: From regular expressions to DFA\u2019s using compressed NFA\u2019s. Theor. Comput. Sci.\u00a0178(1-2), 1\u201336 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.3233\/FUN-2001-45303","volume":"45","author":"J.M. Champarnaud","year":"2001","unstructured":"Champarnaud, J.M., Ziadi, D.: From Mirkin\u2019s prebases to Antimirov\u2019s word partial derivatives. Fundam. Inform.\u00a045(3), 195\u2013205 (2001)","journal-title":"Fundam. Inform."},{"key":"9_CR9","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. Theoret. Comput. Sci.\u00a0289, 137\u2013163 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR10","volume-title":"Analytic Combinatorics","author":"P. Flajolet","year":"2008","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2008)"},{"key":"9_CR11","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":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-14455-4_3","volume-title":"Developments in Language Theory","author":"M. Holzer","year":"2010","unstructured":"Holzer, M., Kutrib, M.: The complexity of regular(-like) expressions. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol.\u00a06224, pp. 16\u201330. Springer, Heidelberg (2010)"},{"key":"9_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1844-9","volume-title":"Automata and Computability","author":"D.C. Kozen","year":"1997","unstructured":"Kozen, D.C.: Automata and Computability. Springer, Heidelberg (1997)"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Leiss, E.: Constructing a finite automaton for a given regular expression. SIGACT News\u00a012(3) (September 1980)","DOI":"10.1145\/1008861.1008870"},{"key":"9_CR15","first-page":"51","volume":"5","author":"B.G. Mirkin","year":"1966","unstructured":"Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Engineering Cybernetics\u00a05, 51\u201357 (1966)","journal-title":"Engineering Cybernetics"},{"key":"9_CR16","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. IEEE Transactions on Electronic Computers\u00a09, 39\u201347 (1960)","journal-title":"IEEE Transactions on Electronic Computers"},{"key":"9_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-00982-2_53","volume-title":"Language and Automata Theory and Applications","author":"C. Nicaud","year":"2009","unstructured":"Nicaud, C.: On the average size of glushkov\u2019s automata. In: Dediu, A., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 626\u2013637. Springer, Heidelberg (2009)"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/3-540-63174-7_9","volume-title":"Automata Implementation","author":"J.-L. Ponty","year":"1997","unstructured":"Ponty, J.-L., Ziadi, D., Champarnaud, J.-M.: A new quadratic algorithm to convert a regular expression into an automaton. In: Raymond, D.R., Yu, S., Wood, D. (eds.) WIA 1996. LNCS, vol.\u00a01260, pp. 109\u2013119. Springer, Heidelberg (1997)"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J.: Elements of Automata Theory. CUP (2009)","DOI":"10.1017\/CBO9781139195218"}],"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-22321-1_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T03:13:58Z","timestamp":1741317238000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22321-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642223204","9783642223211"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22321-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}