{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T14:56:45Z","timestamp":1778943405232,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T00:00:00Z","timestamp":1580774400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T00:00:00Z","timestamp":1580774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00236-020-00366-7","type":"journal-article","created":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T15:03:04Z","timestamp":1580828584000},"page":"195-229","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A deterministic parsing algorithm for ambiguous regular expressions"],"prefix":"10.1007","volume":"58","author":[{"given":"Angelo","family":"Borsotti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5294-6840","authenticated-orcid":false,"given":"Luca","family":"Breveglieri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Crespi Reghizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Morzenti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,4]]},"reference":[{"key":"366_CR1","doi-asserted-by":"crossref","unstructured":"Aaraj, N., Raghunathan, A., Jha, N.K.: Dynamic binary instrumentation-based framework for malware defense. In: Zamboni, D. (ed.) DIMVA, LNCS, vol. 5137, pp. 64\u201387. Springer (2008)","DOI":"10.1007\/978-3-540-70542-0_4"},{"key":"366_CR2","doi-asserted-by":"crossref","unstructured":"Allauzen, C., Mohri, M.: A unified construction of the Glushkov, Follow, and Antimirov automata. In: Kralovic, R., Urzyczyn, P. (eds.) MFCS, LNCS, vol. 4162, pp. 110\u2013121. Springer (2006)","DOI":"10.1007\/11821069_10"},{"issue":"1","key":"366_CR3","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. 48(1), 117\u2013126 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"366_CR4","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\u2013Sethi algorithm. Theor. Comput. Sci. 155(2), 439\u2013446 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"366_CR5","unstructured":"Bille, P., G\u00f8rtz, I.L.: From regular expression matching to parsing. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) MFCS, LIPIcs, vol. 138, pp. 71:1\u201371:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"2","key":"366_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1109\/T-C.1971.223204","volume":"C\u201320","author":"R Book","year":"1971","unstructured":"Book, R., Even, S., Greibach, S., Ott, G.: Ambiguity in graphs and expressions. IEEE Trans. Comput. C\u201320(2), 149\u2013153 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"366_CR7","doi-asserted-by":"crossref","unstructured":"Borsotti, A., Breveglieri, L., Crespi Reghizzi, S., Morzenti, A.: From ambiguous regular expressions to deterministic parsing automata. In: Drewes, F. (ed.) CIAA, LNCS, vol. 9223, pp. 35\u201348. Springer (2015)","DOI":"10.1007\/978-3-319-22360-5_4"},{"key":"366_CR8","doi-asserted-by":"crossref","unstructured":"Borsotti, A., Breveglieri, L., Crespi Reghizzi, S., Morzenti, A.: A benchmark production tool for regular expressions. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G. (eds.) CIAA, LNCS, vol. 11601, pp. 95\u2013107. Springer (2019)","DOI":"10.1007\/978-3-030-23679-3_8"},{"key":"366_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04879-2","volume-title":"Formal Languages and Compilation. Texts in Computer Science","author":"S Crespi Reghizzi","year":"2019","unstructured":"Crespi Reghizzi, S., Breveglieri, L., Morzenti, A.: Formal Languages and Compilation. Texts in Computer Science, 3rd edn. Springer, Berlin (2019)","edition":"3"},{"issue":"2","key":"366_CR10","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s002360000037","volume":"37","author":"D Dub\u00e8","year":"2000","unstructured":"Dub\u00e8, D., Feeley, M.: Efficiently building a parse tree from a regular expression. Acta Inf. 37(2), 121\u2013144 (2000)","journal-title":"Acta Inf."},{"key":"366_CR11","doi-asserted-by":"crossref","unstructured":"Frisch, A., Cardelli, L.: Greedy regular expression matching. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP, LNCS, vol. 3142, pp. 618\u2013629. Springer (2004)","DOI":"10.1007\/978-3-540-27836-8_53"},{"key":"366_CR12","doi-asserted-by":"crossref","unstructured":"Grathwohl, N., Henglein, F., Nielsen, L., Rasmussen, U.: Two-pass greedy regular expression parsing. In: Konstantinidis, S. (ed.) CIAA, LNCS, vol. 7982, pp. 60\u201371. Springer (2013)","DOI":"10.1007\/978-3-642-39274-0_7"},{"issue":"8","key":"366_CR13","doi-asserted-by":"publisher","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\u2014a summary on descriptional complexity. Int. J. Found. Comput. Sci. 26(8), 1009\u20131040 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"366_CR14","doi-asserted-by":"crossref","unstructured":"Haber, S., Horne, W., Manadhata, P., Mowbray, M., Rao, P.: Efficient submatch extraction for practical regular expressions. In: Dediu, A.H., Vide, C.M., Truthe, B. (eds.) LATA, LNCS, vol. 7810, pp. 323\u2013334. Springer (2013)","DOI":"10.1007\/978-3-642-37064-9_29"},{"key":"366_CR15","unstructured":"IEEE: std. 1003.2, POSIX, regular expression notation, section 2.8 (1992)"},{"issue":"8","key":"366_CR16","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1002\/spe.4380210803","volume":"21","author":"S Kearns","year":"1991","unstructured":"Kearns, S.: Extending regular expressions with context operators and parse extraction. Softw. Pract. Exp. 21(8), 787\u2013804 (1991)","journal-title":"Softw. Pract. Exp."},{"key":"366_CR17","unstructured":"Laurikari, V.: NFAs with tagged transitions, their conversion to deterministic automata and application to regular expressions. In: de\u00a0la Fuente, P. (ed.) SPIRE, pp. 181\u2013187. IEEE Computer Society (2000)"},{"key":"366_CR18","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"key":"366_CR19","doi-asserted-by":"crossref","unstructured":"Nielsen, L., Henglein, F.: Bit-coded regular expression parsing. In: Dediu, A.H., Inenaga, S., C.M. (eds.) LATA, LNCS, vol. 6638, pp. 402\u2013413. Springer (2011)","DOI":"10.1007\/978-3-642-21254-3_32"},{"key":"366_CR20","doi-asserted-by":"crossref","unstructured":"Okui, S., Suzuki, T.: Disambiguation in regular expression matching via position automata with augmented transitions. In: Domaratzki, M., Salomaa, K. (eds.) CIAA, LNCS, vol. 6482, pp. 231\u2013240. Springer (2010)","DOI":"10.1007\/978-3-642-18098-9_25"},{"key":"366_CR21","first-page":"e1248","volume":"3","author":"N Schwarz","year":"2015","unstructured":"Schwarz, N., Karper, A., Nierstrasz, O.: Efficiently extracting full parse trees using regular expressions with capture groups. PeerJ PrePrints 3, e1248 (2015)","journal-title":"PeerJ PrePrints"},{"key":"366_CR22","doi-asserted-by":"crossref","unstructured":"Sulzmann, M., Lu, K.Z.M.: POSIX regular expression parsing with derivatives. In: Codish, M., Sumii, E. (eds.) FLOPS, LNCS, vol. 8475, pp. 203\u2013220. Springer (2014)","DOI":"10.1007\/978-3-319-07151-0_13"},{"issue":"5","key":"366_CR23","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1142\/S0129054117400068","volume":"28","author":"M Sulzmann","year":"2017","unstructured":"Sulzmann, M., Lu, K.Z.M.: Derivative-based diagnosis of regular expression ambiguity. Int. J. Found. Comput. Sci. 28(5), 543\u2013562 (2017)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"366_CR24","unstructured":"Watson, B.: A taxonomy of finite automata construction algorithms. Technical Report, Computing Science Notes, Technische Univ. Eindhoven (1993)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00366-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-020-00366-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00366-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,15]],"date-time":"2021-05-15T08:03:31Z","timestamp":1621065811000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-020-00366-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,4]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["366"],"URL":"https:\/\/doi.org\/10.1007\/s00236-020-00366-7","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,4]]},"assertion":[{"value":"24 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}