{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:39:28Z","timestamp":1768707568634,"version":"3.49.0"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319628080","type":"print"},{"value":"9783319628097","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-62809-7_9","type":"book-chapter","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T08:37:57Z","timestamp":1500539877000},"page":"134-146","source":"Crossref","is-referenced-by-count":3,"title":["On the Mother of All Automata: The Position Automaton"],"prefix":"10.1007","author":[{"given":"Sabine","family":"Broda","sequence":"first","affiliation":[]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[]},{"given":"Eva","family":"Maia","sequence":"additional","affiliation":[]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/11821069_10","volume-title":"Mathematical Foundations of Computer Science 2006","author":"C Allauzen","year":"2006","unstructured":"Allauzen, C., Mohri, M.: A unified construction of the glushkov, follow, and antimirov automata. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 110\u2013121. Springer, Heidelberg (2006). doi: 10.1007\/11821069_10"},{"issue":"2","key":"9_CR2","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"VM Antimirov","year":"1996","unstructured":"Antimirov, V.M.: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155(2), 291\u2013319 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR3","unstructured":"Asperti, A., Coen, C.S., Tassi, E.: Regular expressions, au point. CoRR abs\/1010.2604. http:\/\/arxiv.org\/abs\/1010.2604 (2010)"},{"key":"9_CR4","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Mathematical Theory of Automata, MRI Symposia Series, pp. 529\u2013561. Polytechnic Press, Polytechnic Institute of Brooklyn, NY, 12 (1962)"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J Brzozowski","year":"1964","unstructured":"Brzozowski, J.: Derivatives of regular expressions. J. Assoc. Comput. Mach. 11, 481\u2013494 (1964)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"9_CR6","doi-asserted-by":"crossref","first-page":"195","DOI":"10.3233\/FUN-2001-45303","volume":"45","author":"JM Champarnaud","year":"2001","unstructured":"Champarnaud, J.M., Ziadi, D.: From Mirkin\u2019s prebases to Antimirov\u2019s word partial derivatives. Fundam. Inform. 45(3), 195\u2013205 (2001)","journal-title":"Fundam. Inform."},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0304-3975(01)00267-5","volume":"289","author":"JM Champarnaud","year":"2002","unstructured":"Champarnaud, J.M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci. 289, 137\u2013163 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-642-27654-5_27","volume-title":"Computation, Physics and Beyond","author":"H Chen","year":"2012","unstructured":"Chen, H., Yu, S.: Derivatives of regular expressions and an application. In: Dinneen, M.J., Khoussainov, B., Nies, A. (eds.) WTCS 2012. LNCS, vol. 7160, pp. 343\u2013356. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-27654-5_27"},{"key":"9_CR9","unstructured":"Giammarresi, D., Ponty, J.L., Wood, D.: Glushkov and Thompson constructions: A synthesis. HKUST TCSC-98-11, The Department of Science and Engineering, Theoretical Cmputer Science Group, The Hong Kong University of Science and Technology (1998)"},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","volume":"16","author":"VM Glushkov","year":"1961","unstructured":"Glushkov, V.M.: The abstract theory of automata. Russ. Math. Surveys 16, 1\u201353 (1961)","journal-title":"Russ. Math. Surveys"},{"issue":"8","key":"9_CR11","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1142\/S0129054115400110","volume":"26","author":"H Gruber","year":"2015","unstructured":"Gruber, H., Holzer, M.: From finite automata to regular expressions and back\u2013a summary on descriptional complexity. Intern. J. Found. Comput. Sci. 26(8), 1009\u20131040 (2015)","journal-title":"Intern. J. Found. Comput. Sci."},{"issue":"1","key":"9_CR12","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/S0890-5401(03)00090-7","volume":"186","author":"L Ilie","year":"2003","unstructured":"Ilie, L., Yu, S.: Follow automata. Inf. Comput. 186(1), 140\u2013162 (2003)","journal-title":"Inf. Comput."},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-319-20028-6_26","volume-title":"Evolving Computability","author":"E Maia","year":"2015","unstructured":"Maia, E., Moreira, N., Reis, R.: Prefix and right-partial derivative automata. In: Beckmann, A., Mitrana, V., Soskova, M. (eds.) CiE 2015. LNCS, vol. 9136, pp. 258\u2013267. Springer, Cham (2015). doi: 10.1007\/978-3-319-20028-6_26"},{"key":"9_CR14","doi-asserted-by":"crossref","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 Trans. Comput. 9, 39\u201347 (1960)","journal-title":"IEEE Trans. Comput."},{"key":"9_CR15","first-page":"51","volume":"5","author":"BG Mirkin","year":"1966","unstructured":"Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Eng. Cybern. 5, 51\u201357 (1966)","journal-title":"Eng. Cybern."},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-319-08970-6_29","volume-title":"Interactive Theorem Proving","author":"T Nipkow","year":"2014","unstructured":"Nipkow, T., Traytel, D.: Unified decision procedures for regular expression equivalence. In: Klein, G., Gamboa, R. (eds.) ITP 2014. LNCS, vol. 8558, pp. 450\u2013466. Springer, Cham (2014). doi: 10.1007\/978-3-319-08970-6_29"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009)","DOI":"10.1017\/CBO9781139195218"},{"issue":"6","key":"9_CR18","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson, K.: Regular expression search algorithm. Commun. ACM 11(6), 410\u2013422 (1968)","journal-title":"Commun. ACM"},{"key":"9_CR19","unstructured":"Yamamoto, H.: A new finite automaton construction for regular expressions. In: Bensch, S., Freund, R., Otto, F. (eds.) 6th NCMA. vol. 304, pp. 249\u2013264 (2014)"}],"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-319-62809-7_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T16:40:14Z","timestamp":1750783214000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-62809-7_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319628080","9783319628097"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62809-7_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}