{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T18:02:24Z","timestamp":1784484144013,"version":"3.55.0"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032313478","type":"print"},{"value":"9783032313485","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"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":[[2027]]},"DOI":"10.1007\/978-3-032-31348-5_27","type":"book-chapter","created":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:11Z","timestamp":1784482151000},"page":"405-420","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficiently Finding All Shortest Absent Subsequences in\u00a0a\u00a0String"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8928-2928","authenticated-orcid":false,"given":"Tina","family":"Ringleb","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7509-8135","authenticated-orcid":false,"given":"Stefan","family":"Siemer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-2243-9113","authenticated-orcid":false,"given":"Maximilian","family":"Winkler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,20]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: FOCS 2015, pp. 59\u201378 (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"27_CR2","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Ko\u00df, T., Manea, F., Nowotka, D.: $$k$$-universality of regular languages. In: ISAAC 2023. LIPIcs, vol. 283, pp. 4:1\u20134:21 (2023)"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Manea, F., Sarnighausen-Cahn, P., Wiedenh\u00f6ft, M.: Tight bounds for the number of absent subsequences. In: FCT 2025. LNCS, vol. 16106, pp. 15\u201329 (2025)","DOI":"10.1007\/978-3-032-04700-7_2"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Adamson, D., Gawrychowski, P., Manea, F.: Enumerating m-length walks in directed graphs with constant delay. In: LATIN 2024. LNCS, vol. 14578, pp. 35\u201350 (2024)","DOI":"10.1007\/978-3-031-55598-5_3"},{"key":"27_CR5","unstructured":"Amarilli, A., Monet, M.: Enumerating regular languages with bounded delay. In: STACS 2023. LIPIcs, vol. 254, pp. 8:1\u20138:18 (2023)"},{"key":"27_CR6","unstructured":"Badkobeh, G., Charalampopoulos, P., Pissis, S.P.: Internal shortest absent word queries. In: CPM 2021. LIPIcs, vol. 191, pp. 6:1\u20136:18 (2021)"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: DLT 2020. pp. 14\u201328. LNCS, Cham (2020)","DOI":"10.1007\/978-3-030-48516-0_2"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: SPIRE 2000, pp. 39\u201348 (2000)","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"27_CR9","unstructured":"Bernardini, G., Marchetti-Spaccamela, A., Pissis, S.P., Stougie, L., Sweering, M.: Constructing strings avoiding forbidden substrings. In: CPM 2021. LIPIcs, vol. 191, pp. 9:1\u20139:18 (2021)"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2012.03.029","volume":"443","author":"P Bille","year":"2012","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Wind, D.K.: String matching with variable length gaps. Theoretical Comput. Sci. 443, 25\u201334 (2012)","journal-title":"Theoretical Comput. Sci."},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Multivariate fine-grained complexity of longest common subsequence. In: SODA 2018, pp. 1216\u20131235 (2018)","DOI":"10.1137\/1.9781611975031.79"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ic.2018.06.002","volume":"262","author":"P Charalampopoulos","year":"2018","unstructured":"Charalampopoulos, P., Crochemore, M., Fici, G., Merca\u015f, R., Pissis, S.P.: Alignment-free sequence comparison using absent words. Inf. Comput. 262, 57\u201368 (2018)","journal-title":"Inf. Comput."},{"key":"27_CR13","unstructured":"Day, J.D., Fleischmann, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: The edit distance to $$k$$-subsequence universality. In: STACS 2021. LIPIcs, vol. 187, pp. 25:1\u201325:19 (2021)"},{"key":"27_CR14","unstructured":"Fazekas, S.Z., Ko\u00df, T., Manea, F., Mercas, R., Specht, T.: Subsequence matching and analysis problems for formal languages. In: ISAAC 2024. LIPIcs, vol. 322, pp. 28:1\u201328:23 (2024)"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., Haschke, L., H\u00f6fer, J., Huch, A., Mayrock, A., Nowotka, D.: Nearly k-universal words - investigating a part of Simon\u2019s congruence. Theor. Comput. Sci. 974, 114113 (2023)","DOI":"10.1016\/j.tcs.2023.114113"},{"issue":"1","key":"27_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"ML Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discrete Math. 11(1), 29\u201335 (1975)","journal-title":"Discrete Math."},{"issue":"1","key":"27_CR17","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"ML Fredman","year":"1986","unstructured":"Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: a new form of self-adjusting heap. Algorithmica 1(1), 111\u2013129 (1986)","journal-title":"Algorithmica"},{"key":"27_CR18","unstructured":"Frochaux, A., Kleest-Mei\u00dfner, S.: Puzzling over subsequence-query extensions: Disjunction and generalised gaps. In: AMW 2023. CEUR Workshop Proceedings, vol. 3409 (2023)"},{"key":"27_CR19","unstructured":"Fujishige, Y., Tsujimaru, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing DAWGs and minimal absent words in linear time for integer alphabets. In: MFCS 2016. LIPIcs, vol. 58. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"27_CR20","unstructured":"Gawrychowski, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Efficiently testing Simon\u2019s congruence. In: STACS 2021. LIPIcs, vol. 187, pp. 34:1\u201334:18 (2021)"},{"issue":"1","key":"27_CR21","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00778-019-00557-w","volume":"29","author":"N Giatrakos","year":"2020","unstructured":"Giatrakos, N., Alevizos, E., Artikis, A., Deligiannakis, A., Garofalakis, M.N.: Complex event recognition in the big data era: a survey. VLDB J. 29(1), 313\u2013352 (2020)","journal-title":"VLDB J."},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Halfon, S., Schnoebelen, P., Zetzsche, G.: Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In: LICS 2017, pp. 1\u201312 (2017)","DOI":"10.1109\/LICS.2017.8005141"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"H\u00e9brard, J.J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theoretical Comput. Sci. 82(1), 35\u201349 (1991)","DOI":"10.1016\/0304-3975(91)90170-7"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages and the complexity of the logic of subwords. Log. Methods Comput. Sci. 15(2) (2019)","DOI":"10.23638\/LMCS-15(2:6)2019"},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"Kitaev, S.: Patterns in Permutations and Words. Springer (2011)","DOI":"10.1007\/978-3-642-17333-2"},{"key":"27_CR26","unstructured":"Kleest-Mei\u00dfner, S., Sattler, R., Schmid, M.L., Schweikardt, N., Weidlich, M.: Discovering event queries from traces: laying foundations for subsequence-queries with wildcards and gap-size constraints. In: ICDT 2022. LIPIcs, vol. 220, pp. 18:1\u201318:21 (2022)"},{"key":"27_CR27","unstructured":"Kleest-Mei\u00dfner, S., Sattler, R., Schmid, M.L., Schweikardt, N., Weidlich, M.: Discovering multi-dimensional subsequence queries from traces - from theory to practice. In: BTW 2023. LNI, vol. P-331, pp. 511\u2013533 (2023)"},{"key":"27_CR28","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 4A: Combinatorial Algorithms, Part 1. Addison-Wesley (2014)"},{"key":"27_CR29","doi-asserted-by":"crossref","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Absent subsequences in words. In: RP 2021. LNCS, vol. 13035, pp. 115\u2013131 (2021)","DOI":"10.1007\/978-3-030-89716-1_8"},{"issue":"3\u20134","key":"27_CR30","first-page":"199","volume":"189","author":"M Kosche","year":"2022","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Absent subsequences in words. Fundam. Informaticae 189(3\u20134), 199\u2013240 (2022)","journal-title":"Absent subsequences in words. Fundam. Informaticae"},{"key":"27_CR31","doi-asserted-by":"crossref","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Combinatorial algorithms for subsequence matching: a survey. In: NCMA 2022. EPTCS, vol. 367, pp. 11\u201327 (2022)","DOI":"10.4204\/EPTCS.367.2"},{"key":"27_CR32","doi-asserted-by":"crossref","unstructured":"Li, C., Yang, Q., Wang, J., Li, M.: Efficient mining of gap-constrained subsequences and its various applications. ACM TKDD 6(1), 2:1\u20132:39 (2012)","DOI":"10.1145\/2133360.2133362"},{"key":"27_CR33","unstructured":"Manea, F., Ringleb, T., Siemer, S., Winkler, M.: Efficiently finding all minimal and shortest absent subsequences in a string. CoRR abs\/2504.21471 (2025)"},{"key":"27_CR34","doi-asserted-by":"crossref","unstructured":"Pin, J.: The influence of Imre Simon\u2019s work in the theory of automata, languages and semigroups. Semigroup Forum 98, 1\u20138 (2019)","DOI":"10.1007\/s00233-019-09999-8"},{"issue":"1","key":"27_CR35","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0096-0551(79)90009-2","volume":"4","author":"WE Riddle","year":"1979","unstructured":"Riddle, W.E.: An approach to software system modelling and analysis. Comput. Lang. 4(1), 49\u201366 (1979)","journal-title":"Comput. Lang."},{"key":"27_CR36","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2015.07.025","volume":"601","author":"M Rigo","year":"2015","unstructured":"Rigo, M., Salimov, P.: Another generalization of abelian equivalence: binomial complexity of infinite words. Theoret. Comput. Sci. 601, 47\u201357 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR37","doi-asserted-by":"crossref","unstructured":"Romik, D.: The Surprising Mathematics of Longest Increasing Subsequences. Cambridge (2015)","DOI":"10.1017\/CBO9781139872003"},{"issue":"2","key":"27_CR38","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.tcs.2005.03.024","volume":"340","author":"A Salomaa","year":"2005","unstructured":"Salomaa, A.: Connections between subwords and certain matrix mappings. Theoret. Comput. Sci. 340(2), 188\u2013203 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"27_CR39","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1109\/TSE.1978.231501","volume":"4","author":"AC Shaw","year":"1978","unstructured":"Shaw, A.C.: Software descriptions with flow expressions. IEEE Trans. Softw. Eng. 4(3), 242\u2013254 (1978)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"27_CR40","unstructured":"Simon, I.: Hierarchies of events with dot-depth one - Ph.D. thesis (1972)"},{"key":"27_CR41","doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages. pp. 214\u2013222. LNCS, Berlin, Heidelberg (1975)","DOI":"10.1007\/3-540-07407-4_23"},{"key":"27_CR42","unstructured":"Simon, I.: Words distinguished by their subwords (extended abstract). In: WORDS 2003. TUCS General Publication, vol. 27, pp. 6\u201313 (2003)"},{"key":"27_CR43","doi-asserted-by":"crossref","unstructured":"Tron\u00edcek, Z.: On problems related to absent subsequences. In: COCOA 2023. LNCS, vol. 14462, pp. 351\u2013363 (2023)","DOI":"10.1007\/978-3-031-49614-1_26"},{"key":"27_CR44","unstructured":"Wasa, K.: Enumeration of enumeration algorithms. CoRR abs\/1605.05102 (2016)"},{"key":"27_CR45","unstructured":"Zetzsche, G.: The complexity of downward closure comparisons. In: ICALP 2016. LIPIcs, vol. 55, pp. 123:1\u2013123:14 (2016)"},{"key":"27_CR46","doi-asserted-by":"crossref","unstructured":"Zhang, H., Diao, Y., Immerman, N.: On complexity and optimization of expensive queries in complex event processing. In: SIGMOD 2014, pp. 217\u2013228 (2014)","DOI":"10.1145\/2588555.2593671"}],"container-title":["Lecture Notes in Computer Science","Timeless Machines: Computability Across Eras"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31348-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:14Z","timestamp":1784482154000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31348-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,20]]},"ISBN":["9783032313478","9783032313485"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31348-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,20]]},"assertion":[{"value":"20 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}