{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T17:39:43Z","timestamp":1793295583234,"version":"4.5.0"},"publisher-location":"Cham","reference-count":58,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032311764","type":"print"},{"value":"9783032359674","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-35967-4_11","type":"book-chapter","created":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T13:39:54Z","timestamp":1792762794000},"page":"151-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficiently Finding Minimal 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,8,5]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 59\u201378 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.14","DOI":"10.1109\/FOCS.2015.14"},{"key":"11_CR2","doi-asserted-by":"publisher","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Ko\u00df, T., Manea, F., Nowotka, D.: $$k$$-universality of regular languages. In: Iwata, S., Kakimura, N. (eds.) 34th International Symposium on Algorithms and Computation (ISAAC 2023). LIPIcs, vol.\u00a0283, pp. 4:1\u20134:21 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2023.4, full version: https:\/\/arxiv.org\/abs\/2311.10658","DOI":"10.4230\/LIPIcs.ISAAC.2023.4"},{"key":"11_CR3","doi-asserted-by":"publisher","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Manea, F., Sarnighausen-Cahn, P., Wiedenh\u00f6ft, M.: Tight bounds for the number of absent subsequences. In: Jez, A., Otop, J. (eds.) Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wroc\u0142aw, Poland, September 15-17, 2025, Proceedings. LNCS, vol. 16106, pp. 15\u201329. Springer (2025). https:\/\/doi.org\/10.1007\/978-3-032-04700-7_2","DOI":"10.1007\/978-3-032-04700-7_2"},{"key":"11_CR4","doi-asserted-by":"publisher","unstructured":"Adamson, D., Gawrychowski, P., Manea, F.: Enumerating m-length walks in directed graphs with constant delay. In: Soto, J.A., Wiese, A. (eds.) LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I. Lecture Notes in Computer Science, vol. 14578, pp. 35\u201350. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-55598-5_3","DOI":"10.1007\/978-3-031-55598-5_3"},{"key":"11_CR5","doi-asserted-by":"publisher","unstructured":"Amarilli, A., Monet, M.: Enumerating regular languages with bounded delay. In: Berenbrink, P., Bouyer, P., Dawar, A., Kant\u00e9, M.M. (eds.) 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany. LIPIcs, vol.\u00a0254, pp. 8:1\u20138:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2023.8","DOI":"10.4230\/LIPICS.STACS.2023.8"},{"key":"11_CR6","doi-asserted-by":"publisher","unstructured":"Artikis, A., Margara, A., Ugarte, M., Vansummeren, S., Weidlich, M.: Complex event recognition languages: tutorial. In: Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems, DEBS 2017, Barcelona, Spain, June 19-23, 2017, pp. 7\u201310 (2017). https:\/\/doi.org\/10.1145\/3093742.3095106","DOI":"10.1145\/3093742.3095106"},{"key":"11_CR7","doi-asserted-by":"publisher","unstructured":"Badkobeh, G., Charalampopoulos, P., Pissis, S.P.: Internal shortest absent word queries. In: 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wroc\u0142aw, Poland. LIPIcs, vol.\u00a0191, pp. 6:1\u20136:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2021.6","DOI":"10.4230\/LIPICS.CPM.2021.6"},{"key":"11_CR8","doi-asserted-by":"publisher","unstructured":"Baeza-Yates, R.A.: Searching subsequences. Theor. Comput. Sci. 78(2), 363\u2013376 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90358-9","DOI":"10.1016\/0304-3975(91)90358-9"},{"key":"11_CR9","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings. LNCS, vol.\u00a01776, pp. 88\u201394. Springer (2000). https:\/\/doi.org\/10.1007\/10719839_9","DOI":"10.1007\/10719839_9"},{"key":"11_CR10","doi-asserted-by":"publisher","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: de\u00a0la Fuente, P. (ed.) Seventh International Symposium on String Processing and Information Retrieval, SPIRE 2000, A Coru\u00f1a, Spain, September 27-29, 2000, pp. 39\u201348 (2000). https:\/\/doi.org\/10.1109\/SPIRE.2000.878178","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"11_CR11","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Marchetti-Spaccamela, A., Pissis, S.P., Stougie, L., Sweering, M.: Constructing strings avoiding forbidden substrings. In: 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wroc\u0142aw, Poland. LIPIcs, vol.\u00a0191, pp. 9:1\u20139:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2021.9","DOI":"10.4230\/LIPICS.CPM.2021.9"},{"key":"11_CR12","doi-asserted-by":"publisher","unstructured":"Bille, P., Farach-Colton, M.: Fast and compact regular expression matching. Theor. Comput. Sci. 409(3), 486\u2013496 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.08.042","DOI":"10.1016\/j.tcs.2008.08.042"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/J.JDA.2017.05.001","volume":"44","author":"P Bille","year":"2017","unstructured":"Bille, P., G\u00f8rtz, I.L., Skjoldjensen, F.R.: Subsequence automata with default transitions. J. Discrete Algorithms 44, 48\u201355 (2017). https:\/\/doi.org\/10.1016\/J.JDA.2017.05.001","journal-title":"J. Discrete Algorithms"},{"key":"11_CR14","doi-asserted-by":"publisher","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Wind, D.K.: String matching with variable length gaps. Theor. Comput. Sci. 443, 25\u201334 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.029","DOI":"10.1016\/j.tcs.2012.03.029"},{"key":"11_CR15","doi-asserted-by":"publisher","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Multivariate fine-grained complexity of longest common subsequence. In: Proc. SODA 2018, pp. 1216\u20131235 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.79","DOI":"10.1137\/1.9781611975031.79"},{"key":"11_CR16","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). https:\/\/doi.org\/10.1016\/j.ic.2018.06.002","journal-title":"Inf. Comput."},{"issue":"3\u20134","key":"11_CR17","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S1570-8667(03)00029-7","volume":"1","author":"M Crochemore","year":"2003","unstructured":"Crochemore, M., Melichar, B., Tron\u00ed\u010dek, Z.: Directed acyclic subsequence graph \u2013 overview. J. Discrete Algorithms 1(3\u20134), 255\u2013280 (2003). https:\/\/doi.org\/10.1016\/S1570-8667(03)00029-7","journal-title":"J. Discrete Algorithms"},{"key":"11_CR18","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Mignosi, F., Restivo, A.: Automata and forbidden words. Inf. Process. Lett. 67(3), 111\u2013117 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(98)00104-5","DOI":"10.1016\/S0020-0190(98)00104-5"},{"issue":"11","key":"11_CR19","doi-asserted-by":"publisher","first-page":"1756","DOI":"10.1109\/5.892711","volume":"88","author":"M Crochemore","year":"2000","unstructured":"Crochemore, M., Mignosi, F., Restivo, A., Salemi, S.: Data compression using antidictionaries. Proc. IEEE 88(11), 1756\u20131768 (2000). https:\/\/doi.org\/10.1109\/5.892711","journal-title":"Proc. IEEE"},{"key":"11_CR20","doi-asserted-by":"publisher","unstructured":"Fazekas, S.Z., Ko\u00df, T., Manea, F., Mercas, R., Specht, T.: Subsequence matching and analysis problems for formal languages. In: 35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia. LIPIcs, vol.\u00a0322, pp. 28:1\u201328:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.ISAAC.2024.28","DOI":"10.4230\/LIPICS.ISAAC.2024.28"},{"key":"11_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2023.114113","volume":"974","author":"P Fleischmann","year":"2023","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). https:\/\/doi.org\/10.1016\/J.TCS.2023.114113","journal-title":"Theor. Comput. Sci."},{"key":"11_CR22","doi-asserted-by":"publisher","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discrete Math. 11(1), 29\u201335 (1975). https:\/\/doi.org\/10.1016\/0012-365X(75)90103-X","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"11_CR23","doi-asserted-by":"publisher","unstructured":"Freydenberger, D.D., Gawrychowski, P., Karhum\u00e4ki, J., Manea, F., Rytter, W.: Testing $$k$$-binomial equivalence. https:\/\/arxiv.org\/abs\/1509.00622, pp. 239\u2013248 (2015). https:\/\/doi.org\/10.48550\/arXiv.1509.00622","DOI":"10.48550\/arXiv.1509.00622"},{"key":"11_CR24","unstructured":"Frochaux, A., Kleest-Mei\u00dfner, S.: Puzzling over subsequence-query extensions: Disjunction and generalised gaps. In: Kimelfeld, B., Martinez, M.V., Angles, R. (eds.) Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023. CEUR Workshop Proceedings, vol.\u00a03409. CEUR-WS.org (2023). https:\/\/ceur-ws.org\/Vol-3409\/paper3.pdf"},{"key":"11_CR25","doi-asserted-by":"publisher","unstructured":"Fujishige, Y., Tsujimaru, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing DAWGs and minimal absent words in linear time for integer alphabets. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.38","DOI":"10.4230\/LIPIcs.MFCS.2016.38"},{"key":"11_CR26","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Efficiently testing Simon\u2019s congruence. In: 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbr\u00fccken, Germany (Virtual Conference), pp. 34:1\u201334:18 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.34","DOI":"10.4230\/LIPIcs.STACS.2021.34"},{"key":"11_CR27","doi-asserted-by":"publisher","unstructured":"Giatrakos, N., Alevizos, E., Artikis, A., Deligiannakis, A., Garofalakis, M.: Complex event recognition in the Big Data era: a survey. VLDB J. 29(1), 313\u2013352 (2020). https:\/\/doi.org\/10.1007\/s00778-019-00557-w","DOI":"10.1007\/s00778-019-00557-w"},{"key":"11_CR28","doi-asserted-by":"publisher","unstructured":"Halfon, S., Schnoebelen, P., Zetzsche, G.: Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In: Proceedings of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS \u201917, pp. 1\u201312 (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005141","DOI":"10.1109\/LICS.2017.8005141"},{"key":"11_CR29","doi-asserted-by":"publisher","unstructured":"H\u00e9brard, J.J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theor. Comput. Sci. 82(1), 35\u201349 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90170-7","DOI":"10.1016\/0304-3975(91)90170-7"},{"key":"11_CR30","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)"},{"key":"11_CR31","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.23638\/LMCS-15(2:6)2019","DOI":"10.23638\/LMCS-15(2:6)2019"},{"key":"11_CR32","doi-asserted-by":"publisher","unstructured":"Kitaev, S.: Patterns in permutations and words. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-17333-2","DOI":"10.1007\/978-3-642-17333-2"},{"key":"11_CR33","doi-asserted-by":"publisher","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: Olteanu, D., Vortmeier, N. (eds.) 25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference). LIPIcs, vol.\u00a0220, pp. 18:1\u201318:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.ICDT.2022.18","DOI":"10.4230\/LIPICS.ICDT.2022.18"},{"key":"11_CR34","doi-asserted-by":"publisher","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: K\u00f6nig-Ries, B., Scherzinger, S., Lehner, W., Vossen, G. (eds.) Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW 2023), 20. Fachtagung des GI-Fachbereichs ,,Datenbanken und Informationssysteme\u201d (DBIS), 06.-10, M\u00e4rz 2023, Dresden, Germany, Proceedings. LNI, vol. P-331, pp. 511\u2013533. Gesellschaft f\u00fcr Informatik e.V. (2023). https:\/\/doi.org\/10.18420\/BTW2023-24","DOI":"10.18420\/BTW2023-24"},{"key":"11_CR35","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley (2014)"},{"key":"11_CR36","doi-asserted-by":"publisher","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Absent subsequences in words. In: Bell, P.C., Totzke, P., Potapov, I. (eds.) Reachability Problems - 15th International Conference, RP 2021, Liverpool, UK, October 25-27, 2021, Proceedings. LNCS, vol. 13035, pp. 115\u2013131 (2021). https:\/\/doi.org\/10.1007\/978-3-030-89716-1_8","DOI":"10.1007\/978-3-030-89716-1_8"},{"issue":"3\u20134","key":"11_CR37","doi-asserted-by":"publisher","first-page":"199","DOI":"10.3233\/FI-222159","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). https:\/\/doi.org\/10.3233\/FI-222159","journal-title":"Absent subsequences in words. Fundam. Informaticae"},{"key":"11_CR38","doi-asserted-by":"publisher","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Combinatorial algorithms for subsequence matching: a survey. In: Bordihn, H., Horv\u00e1th, G., Vaszil, G. (eds.) Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications, NCMA 2022, Debrecen, Hungary, August 26-27, 2022. EPTCS, vol.\u00a0367, pp. 11\u201327. (2022). https:\/\/doi.org\/10.4204\/EPTCS.367.2","DOI":"10.4204\/EPTCS.367.2"},{"key":"11_CR39","doi-asserted-by":"publisher","unstructured":"Li, C., Wang, J.: Efficiently Mining Closed Subsequences with Gap Constraints, pp. 313\u2013322. SIAM (2008). https:\/\/doi.org\/10.1137\/1.9781611972788.28","DOI":"10.1137\/1.9781611972788.28"},{"key":"11_CR40","doi-asserted-by":"publisher","unstructured":"Li, C., Yang, Q., Wang, J., Li, M.: Efficient mining of gap-constrained subsequences and its various applications. ACM Trans. Knowl. Discov.Data 6(1), 2:1\u20132:39 (2012). https:\/\/doi.org\/10.1145\/2133360.2133362","DOI":"10.1145\/2133360.2133362"},{"key":"11_CR41","doi-asserted-by":"publisher","unstructured":"Linton, S., Ru\u0161kuc, N., Vatter, V. (eds.): Permutation Patterns. London Mathematical Society Lecture Note Series, vol.\u00a0376, Cambridge (2010). https:\/\/doi.org\/10.1017\/CBO9780511902499","DOI":"10.1017\/CBO9780511902499"},{"key":"11_CR42","doi-asserted-by":"publisher","unstructured":"Manea, F., Ringleb, T., Siemer, S., Winkler, M.: Efficiently finding all minimal and shortest absent subsequences in a string. CoRR (2025). https:\/\/doi.org\/10.48550\/ARXIV.2504.21471","DOI":"10.48550\/ARXIV.2504.21471"},{"issue":"1","key":"11_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2003.04.001","volume":"68","author":"A Mateescu","year":"2004","unstructured":"Mateescu, A., Salomaa, A., Yu, S.: Subword histories and Parikh matrices. J. Comput. Syst. Sci. 68(1), 1\u201321 (2004). https:\/\/doi.org\/10.1016\/j.jcss.2003.04.001","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"11_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00233-019-09999-8","volume":"98","author":"J\u00c9 Pin","year":"2019","unstructured":"Pin, J.\u00c9.: The influence of Imre Simon\u2019s work in the theory of automata, languages and semigroups. Semigroup Forum 98(1), 1\u20138 (2019). https:\/\/doi.org\/10.1007\/s00233-019-09999-8","journal-title":"Semigroup Forum"},{"issue":"1","key":"11_CR45","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). https:\/\/doi.org\/10.1016\/0096-0551(79)90009-2","journal-title":"Comput. Lang."},{"key":"11_CR46","doi-asserted-by":"publisher","unstructured":"Rigo, M., Salimov, P.: Another generalization of abelian equivalence: binomial complexity of infinite words. Theor. Comput. Sci. 601, 47\u201357 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.07.025","DOI":"10.1016\/j.tcs.2015.07.025"},{"key":"11_CR47","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139872003","author":"D Romik","year":"2015","unstructured":"Romik, D.: The surprising mathematics of longest increasing subsequences. Cambridge (2015). https:\/\/doi.org\/10.1017\/CBO9781139872003","journal-title":"Cambridge"},{"key":"11_CR48","doi-asserted-by":"publisher","unstructured":"Salomaa, A.: Connections between subwords and certain matrix mappings. Theor. Comput. Sci. 340(2), 188\u2013203 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.03.024","DOI":"10.1016\/j.tcs.2005.03.024"},{"key":"11_CR49","doi-asserted-by":"publisher","unstructured":"Shaw, A.C.: Software descriptions with flow expressions. IEEE Trans. Softw. Eng. 4(3), 242\u2013254 (1978). https:\/\/doi.org\/10.1109\/TSE.1978.231501","DOI":"10.1109\/TSE.1978.231501"},{"key":"11_CR50","unstructured":"Simon, I.: Hierarchies of events with dot-depth one - Ph.D. thesis, University of Waterloo (1972)"},{"key":"11_CR51","doi-asserted-by":"publisher","unstructured":"Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) Automata Theory and Formal Languages, pp. 214\u2013222. LNCS, Springer, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07407-4_23","DOI":"10.1007\/3-540-07407-4_23"},{"key":"11_CR52","unstructured":"Simon, I.: Words distinguished by their subwords (extended abstract). In: Proc. WORDS 2003. TUCS General Publication, vol. 27, pp. 6\u201313 (2003)"},{"key":"11_CR53","doi-asserted-by":"publisher","unstructured":"Thorup, M.: Space efficient dynamic stabbing with fast queries. In: Larmore, L.L., Goemans, M.X. (eds.) Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pp. 649\u2013658. ACM (2003). https:\/\/doi.org\/10.1145\/780542.780636","DOI":"10.1145\/780542.780636"},{"key":"11_CR54","doi-asserted-by":"publisher","unstructured":"Tron\u00edcek, Z.: On problems related to absent subsequences. In: Wu, W., Guo, J. (eds.) Combinatorial Optimization and Applications - 17th International Conference, COCOA 2023, Hawaii, HI, USA, December 15-17, 2023, Proceedings, Part II. LNCS, vol. 14462, pp. 351\u2013363. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-49614-1_26","DOI":"10.1007\/978-3-031-49614-1_26"},{"key":"11_CR55","doi-asserted-by":"publisher","unstructured":"Wasa, K.: Enumeration of enumeration algorithms. CoRR (2016). https:\/\/doi.org\/10.48550\/arXiv.1605.05102","DOI":"10.48550\/arXiv.1605.05102"},{"key":"11_CR56","doi-asserted-by":"publisher","unstructured":"Zetzsche, G.: The complexity of downward closure comparisons. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). LIPIcs, vol.\u00a055, pp. 123:1\u2013123:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.123","DOI":"10.4230\/LIPIcs.ICALP.2016.123"},{"key":"11_CR57","doi-asserted-by":"publisher","unstructured":"Zetzsche, G.: Separability by piecewise testable languages and downward closures beyond subwords. In: Dawar, A., Gr\u00e4del, E. (eds.) Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pp. 929\u2013938. ACM (2018). https:\/\/doi.org\/10.1145\/3209108.3209201","DOI":"10.1145\/3209108.3209201"},{"key":"11_CR58","doi-asserted-by":"publisher","unstructured":"Zhang, H., Diao, Y., Immerman, N.: On complexity and optimization of expensive queries in complex event processing. In: International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, pp. 217\u2013228 (2014). https:\/\/doi.org\/10.1145\/2588555.2593671","DOI":"10.1145\/2588555.2593671"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-35967-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T13:39:57Z","timestamp":1792762797000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-3-032-35967-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032311764","9783032359674"],"references-count":58,"aliases":["10.1007\/978-3-032-31176-4_11"],"URL":"https:\/\/doi.org\/10.1007\/978-3-032-35967-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"5 August 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kingston","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","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":"5 May 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/research.cs.queensu.ca\/ciaa2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}