{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:30:29Z","timestamp":1757619029104,"version":"3.44.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031987397"},{"type":"electronic","value":"9783031987403"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-98740-3_18","type":"book-chapter","created":{"date-parts":[[2025,7,17]],"date-time":"2025-07-17T23:48:45Z","timestamp":1752796125000},"page":"242-255","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Pattern Matching with\u00a0Epsilon Transitions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1402-5298","authenticated-orcid":false,"given":"Nicola","family":"Cotumaccio","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,18]]},"reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0029792","volume-title":"Combinatorial Pattern Matching","author":"T Akutsu","year":"1993","unstructured":"Akutsu, T.: A linear time pattern matching algorithm between a string and a tree. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1993. LNCS, vol. 684, pp. 1\u201310. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/BFb0029792"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Alanko, J., Cotumaccio, N., Prezza, N.: Linear-time minimization of Wheeler DFAs. In: 2022 Data Compression Conference (DCC), pp. 53\u201362. IEEE (2022)","DOI":"10.1109\/DCC52660.2022.00013"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Alanko, J., D\u2019Agostino, G., Policriti, A., Prezza, N.: Regular languages meet prefix sorting. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 911\u2013930. SIAM (2020)","DOI":"10.1137\/1.9781611975994.55"},{"key":"18_CR4","unstructured":"Alanko, J.N., Cenzato, D., Cotumaccio, N., Kim, S.H., Manzini, G., Prezza, N.: Computing the LCP array of a labeled graph. In: 35th Annual Symposium on Combinatorial Pattern Matching (2024)"},{"issue":"1","key":"18_CR5","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/jagm.1999.1063","volume":"35","author":"A Amir","year":"2000","unstructured":"Amir, A., Lewenstein, M., Lewenstein, N.: Pattern matching in hypertext. J. Algorithms 35(1), 82\u201399 (2000). https:\/\/doi.org\/10.1006\/jagm.1999.1063","journal-title":"J. Algorithms"},{"issue":"1","key":"18_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s11047-022-09882-6","volume":"21","author":"JA Baaijens","year":"2022","unstructured":"Baaijens, J.A., et al.: Computational graph pangenomics: a tutorial on data structures and their applications. Nat. Comput. 21(1), 81\u2013108 (2022). https:\/\/doi.org\/10.1007\/s11047-022-09882-6","journal-title":"Nat. Comput."},{"key":"18_CR7","doi-asserted-by":"publisher","unstructured":"Bankevich, A., et al.: SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing. J. Comput. Biol. 19(5), 455\u2013477 (2012). https:\/\/doi.org\/10.1089\/cmb.2012.0021. pMID: 22506599","DOI":"10.1089\/cmb.2012.0021"},{"key":"18_CR8","unstructured":"Becker, R., Cotumaccio, N., Kim, S.-H., Prezza, N., Tosoni, C.: Encoding co-lex orders of finite-state automata in linear space. In: 36th Annual Symposium on Combinatorial Pattern Matching, p. 17 (2025)"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-33122-0_18","volume-title":"Algorithms in Bioinformatics","author":"A Bowe","year":"2012","unstructured":"Bowe, A., Onodera, T., Sadakane, K., Shibuya, T.: Succinct de Bruijn graphs. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, pp. 225\u2013235. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33122-0_18"},{"key":"18_CR10","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report (1994)"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Conte, A., Cotumaccio, N., Gagie, T., Manzini, G., Prezza, N., Sciortino, M.: Computing matching statistics on Wheeler DFAs. In: 2023 Data Compression Conference (DCC), pp. 150\u2013159. IEEE (2023)","DOI":"10.1109\/DCC55655.2023.00023"},{"key":"18_CR12","doi-asserted-by":"publisher","unstructured":"Cotumaccio, N.: Graphs can be succinctly indexed for pattern matching in $$O(\\vert E\\vert ^{2}+\\vert V\\vert ^{5\/2})$$ time. In: 2022 Data Compression Conference (DCC), pp. 272\u2013281 (2022). https:\/\/doi.org\/10.1109\/DCC52660.2022.00035","DOI":"10.1109\/DCC52660.2022.00035"},{"key":"18_CR13","unstructured":"Cotumaccio, N.: Prefix sorting DFAs: a recursive algorithm. In: 34th International Symposium on Algorithms and Computation (ISAAC 2023), pp. 22\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"18_CR14","unstructured":"Cotumaccio, N.: A Myhill-Nerode theorem for generalized automata, with applications to pattern matching and compression. In: 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"18_CR15","doi-asserted-by":"publisher","unstructured":"Cotumaccio, N., D\u2019Agostino, G., Policriti, A., Prezza, N.: Co-lexicographically ordering automata and regular languages - part I. J. ACM 70(4) (2023). https:\/\/doi.org\/10.1145\/3607471","DOI":"10.1145\/3607471"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Cotumaccio, N., Gagie, T., K\u00f6ppl, D., Prezza, N.: Space-time trade-offs for the LCP array of Wheeler DFAs. In: International Symposium on String Processing and Information Retrieval, pp. 143\u2013156. Springer (2023)","DOI":"10.1007\/978-3-031-43980-3_12"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Cotumaccio, N., Prezza, N.: On indexing and compressing finite automata. In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pp. 2585\u20132599. Society for Industrial and Applied Mathematics, USA (2021)","DOI":"10.1137\/1.9781611976465.153"},{"key":"18_CR18","unstructured":"Cotumaccio, N., Trubiani, C.: Convex petri nets. In: K\u00f6hler-Bussmeier, M., Moldt, D., R\u00f6lke, H. (eds.) Proceedings of the International Workshop on Petri Nets and Software Engineering 2024 Co-located with the 45th International Conference on Application and Theory of Petri Nets and Concurrency (PETRI NETS 2024), 24\u201325 June 2024, Geneva, Switzerland. CEUR Workshop Proceedings, vol.\u00a03730. CEUR-WS.org (2024)"},{"key":"18_CR19","unstructured":"Cotumaccio, N.: Improved circular dictionary matching. In: 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025), pp. 1\u201318. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2025)"},{"key":"18_CR20","doi-asserted-by":"publisher","unstructured":"Equi, M., Grossi, R., M\u00e4kinen, V., Tomescu, A.I.: On the complexity of string matching for graphs. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, 9\u201312 July 2019, Patras, Greece. LIPIcs, vol.\u00a0132, pp. 55:1\u201355:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.55","DOI":"10.4230\/LIPIcs.ICALP.2019.55"},{"key":"18_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-030-67731-2_44","volume-title":"SOFSEM 2021: Theory and Practice of Computer Science","author":"M Equi","year":"2021","unstructured":"Equi, M., M\u00e4kinen, V., Tomescu, A.I.: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. In: Bure\u0161, T., et al. (eds.) SOFSEM 2021. LNCS, vol. 12607, pp. 608\u2013622. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-67731-2_44"},{"issue":"6","key":"18_CR22","doi-asserted-by":"publisher","first-page":"1586","DOI":"10.1007\/s00453-022-01007-w","volume":"85","author":"M Equi","year":"2023","unstructured":"Equi, M., Norri, T., Alanko, J., Cazaux, B., Tomescu, A.I., M\u00e4kinen, V.: Algorithms and complexity on indexing founder graphs. Algorithmica 85(6), 1586\u20131623 (2023). https:\/\/doi.org\/10.1007\/s00453-022-01007-w","journal-title":"Algorithmica"},{"key":"18_CR23","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM 57(1) (2009). https:\/\/doi.org\/10.1145\/1613676.1613680","DOI":"10.1145\/1613676.1613680"},{"key":"18_CR24","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005). https:\/\/doi.org\/10.1145\/1082036.1082039","DOI":"10.1145\/1082036.1082039"},{"key":"18_CR25","doi-asserted-by":"publisher","unstructured":"Gagie, T., Manzini, G., Sir\u00e9n, J.: Wheeler graphs: A framework for BWT-based data structures. Theor. Comput. Sci. 698, 67\u201378 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.06.016. Algorithms, Strings and Theoretical Approaches in the Big Data Era (In Honor of the 60th Birthday of Professor Raffaele Giancarlo)","DOI":"10.1016\/j.tcs.2017.06.016"},{"key":"18_CR26","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn., Pearson International Edition. Addison-Wesley (2007)"},{"issue":"2","key":"18_CR27","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1089\/cmb.1995.2.291","volume":"2","author":"RM Idury","year":"1995","unstructured":"Idury, R.M., Waterman, M.S.: A new algorithm for DNA sequence assembly. J. comput. biol.: J. Comput. Mol. Cell Biol. 2(2), 291\u2013306 (1995)","journal-title":"J. comput. biol.: J. Comput. Mol. Cell Biol."},{"issue":"2","key":"18_CR28","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977). https:\/\/doi.org\/10.1137\/0206024","journal-title":"SIAM J. Comput."},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-Scale Algorithm Design: Bioinformatics in the Era of High-Throughput Sequencing. Cambridge University Press (2023)","DOI":"10.1017\/9781009341257"},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"Manber, U., Wu, S.: Approximate string matching with arbitrary costs for text and hypertext. In: Advances In Structural And Syntactic Pattern Recognition, pp. 22\u201333. World Scientific (1992)","DOI":"10.1142\/9789812797919_0002"},{"key":"18_CR31","doi-asserted-by":"publisher","unstructured":"Navarro, G.: Improved approximate pattern matching on hypertext. Theor. Comput. Sci. 237(1\u20132), 455\u2013463 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(99)00333-3","DOI":"10.1016\/S0304-3975(99)00333-3"},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Compact Data Structures: A Practical Approach. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781316588284"},{"key":"18_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/3-540-60044-2_51","volume-title":"Combinatorial Pattern Matching","author":"K Park","year":"1995","unstructured":"Park, K., Kim, D.K.: String matching in hypertext. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol. 937, pp. 318\u2013329. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60044-2_51"},{"issue":"17","key":"18_CR34","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"PA Pevzner","year":"2001","unstructured":"Pevzner, P.A., Tang, H., Waterman, M.S.: An Eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci. 98(17), 9748\u20139753 (2001). https:\/\/doi.org\/10.1073\/pnas.171285098","journal-title":"Proc. Natl. Acad. Sci."},{"key":"18_CR35","doi-asserted-by":"publisher","unstructured":"Rautiainen, M., Marschall, T.: Aligning sequences to general graphs in $$ O(V + mE) $$ time. bioRxiv (2017). https:\/\/doi.org\/10.1101\/216127","DOI":"10.1101\/216127"},{"key":"18_CR36","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/978-3-031-06678-8_35","volume-title":"Combinatorial Algorithms","author":"N Rizzo","year":"2022","unstructured":"Rizzo, N., M\u00e4kinen, V.: Linear time construction of indexable Elastic Founder graphs. In: Bazgan, C., Fernau, H. (eds.) Combinatorial Algorithms, pp. 480\u2013493. Springer, Cham (2022)"},{"key":"18_CR37","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), pp. 1\u201311. IEEE (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-98740-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T13:47:36Z","timestamp":1757252856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-98740-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031987397","9783031987403"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-98740-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 July 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bozeman, MT","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"36","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cs.montana.edu\/bhz\/iwoca2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}