{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T15:23:55Z","timestamp":1767021835772,"version":"3.48.0"},"reference-count":71,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"vor","delay-in-days":5,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003385","name":"Georg-August-Universit\u00e4t G\u00f6ttingen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003385","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. (2022), we consider the setting when the distance (i.\u00a0e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. (2022). In all these cases, we present efficient algorithms for determining the length of the longest common constrained subsequence between two given strings, and discuss lower bounds for the respective problems.<\/jats:p>","DOI":"10.1007\/s00224-025-10223-0","type":"journal-article","created":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:49:00Z","timestamp":1749170940000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Longest Common Subsequence with Gap Constraints"],"prefix":"10.1007","volume":"69","author":[{"given":"Duncan","family":"Adamson","sequence":"first","affiliation":[]},{"given":"Paul","family":"Sarnighausen-Cahn","sequence":"additional","affiliation":[]},{"given":"Marius","family":"Dumitran","sequence":"additional","affiliation":[]},{"given":"Maria","family":"Kosche","sequence":"additional","affiliation":[]},{"given":"Tore","family":"Ko\u00df","sequence":"additional","affiliation":[]},{"given":"Florin","family":"Manea","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Siemer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,6]]},"reference":[{"key":"10223_CR1","doi-asserted-by":"publisher","unstructured":"Adamson, D., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Longest common subsequence with gap constraints. In: Frid, A.E., Mercas, R. (eds.) Combinatorics on Words - 14th International Conference, WORDS 2023, Ume\u00e5, Sweden, June 12-16, 2023, Proceedings. Lecture Notes in Computer Science, vol. 13899, pp. 60\u201376. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-33180-0_5","DOI":"10.1007\/978-3-031-33180-0_5"},{"key":"10223_CR2","doi-asserted-by":"publisher","unstructured":"Adamson, D., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Longest common subsequence with gap constraints. CoRR arXiv:2304.05270https:\/\/doi.org\/10.48550\/ARXIV.2304.05270 (2023)","DOI":"10.48550\/ARXIV.2304.05270"},{"key":"10223_CR3","unstructured":"Simon, I.: Hierarchies of Events with Dot-depth One \u2014 Ph.D. Thesis. University of Waterloo, (1972)"},{"key":"10223_CR4","doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Autom. Theor. Form. Lang., 2nd GI Conf. LNCS, vol. 33, pp. 214\u2013222 (1975)","DOI":"10.1007\/3-540-07407-4_23"},{"issue":"4","key":"10223_CR5","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1016\/j.ipl.2014.11.008","volume":"115","author":"P Karandikar","year":"2015","unstructured":"Karandikar, P., Kufleitner, M., Schnoebelen, P.: On the index of Simon\u2019s congruence for piecewise testability. Inf. Process. Lett. 115(4), 515\u2013519 (2015)","journal-title":"Inf. Process. Lett."},{"key":"10223_CR6","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages with applications in logical complexity. In: Proc. CSL 2016. LIPIcs, vol. 62, pp. 37\u201313722 (2016)"},{"key":"10223_CR7","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":"10223_CR8","doi-asserted-by":"crossref","unstructured":"Halfon, S., Schnoebelen, P., Zetzsche, G.: Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In: Proc. LICS 2017, pp. 1\u201312 (2017)","DOI":"10.1109\/LICS.2017.8005141"},{"key":"10223_CR9","doi-asserted-by":"crossref","unstructured":"Kuske, D., Zetzsche, G.: Languages ordered by the subword order. In: Proc. FOSSACS 2019. Lecture Notes in Computer Science, vol. 11425, pp. 348\u2013364 (2019)","DOI":"10.1007\/978-3-030-17127-8_20"},{"key":"10223_CR10","doi-asserted-by":"crossref","unstructured":"Kuske, D.: The subtrace order and counting first-order logic. In: Proc. CSR 2020. Lecture Notes in Computer Science, vol. 12159, pp. 289\u2013302 (2020)","DOI":"10.1007\/978-3-030-50026-9_21"},{"key":"10223_CR11","unstructured":"Zetzsche, G.: The complexity of downward closure comparisons. In: Proc. ICALP 2016. LIPIcs, vol. 55, pp. 123\u2013112314 (2016)"},{"key":"10223_CR12","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. Theor. Comput. Sci. 601, 47\u201357 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"10223_CR13","unstructured":"Freydenberger, D.D., Gawrychowski, P., Karhum\u00e4ki, J., Manea, F., Rytter, W.: Testing $$k$$-binomial equivalence. In: Multidisciplinary Creativity, a Collection of Papers Dedicated to G. Paun 65th Birthday, pp. 239\u2013248 (2015). available in CoRR arXiv:1509.00622"},{"key":"10223_CR14","doi-asserted-by":"crossref","unstructured":"Leroy, J., Rigo, M., Stipulanti, M.: Generalized Pascal triangle for binomial coefficients of words. Electron. J. Combin. 24(1.44), 36 (2017)","DOI":"10.37236\/6581"},{"key":"10223_CR15","doi-asserted-by":"crossref","unstructured":"Lejeune, M., Leroy, J., Rigo, M.: Computing the $$k$$-binomial complexity of the Thue-Morse word. In: Proc. DLT 2019. Lecture Notes in Computer Science, vol. 11647, pp. 278\u2013291 (2019)","DOI":"10.1007\/978-3-030-24886-4_21"},{"key":"10223_CR16","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2011.10.017","volume":"418","author":"S Seki","year":"2012","unstructured":"Seki, S.: Absoluteness of subword inequality is undecidable. Theor. Comput. Sci. 418, 116\u2013120 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10223_CR17","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10223_CR18","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."},{"key":"10223_CR19","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Sankoff, D.: Longest common subsequences of two random sequences. J. Appl. Probab. 12(2), 306\u2013315 (1975). Accessed 22 Feb 2023","DOI":"10.2307\/3212444"},{"issue":"4","key":"10223_CR20","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg, D.S.: Algorithms for the longest common subsequence problem. J. ACM 24(4), 664\u2013675 (1977). https:\/\/doi.org\/10.1145\/322033.322044","journal-title":"J. ACM"},{"issue":"5","key":"10223_CR21","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest subsequences. Commun. ACM 20(5), 350\u2013353 (1977). https:\/\/doi.org\/10.1145\/359581.359603","journal-title":"Commun. ACM"},{"issue":"2","key":"10223_CR22","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"issue":"1","key":"10223_CR23","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20(1), 18\u201331 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90002-1","journal-title":"J. Comput. Syst. Sci."},{"key":"10223_CR24","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00264437","volume":"18","author":"N Nakatsu","year":"1982","unstructured":"Nakatsu, N., Kambayashi, Y., Yajima, S.: A longest common subsequence algorithm suitable for similar text strings. Acta Informatica 18, 171\u2013179 (1982). https:\/\/doi.org\/10.1007\/BF00264437","journal-title":"Acta Informatica"},{"issue":"2","key":"10223_CR25","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"RA Baeza-Yates","year":"1991","unstructured":"Baeza-Yates, R.A.: Searching subsequences. Theor. Comput. Sci. 78(2), 363\u2013376 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"10223_CR26","doi-asserted-by":"publisher","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: 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. IEEE Computer Society (2000). https:\/\/doi.org\/10.1109\/SPIRE.2000.878178","DOI":"10.1109\/SPIRE.2000.878178"},{"issue":"1","key":"10223_CR27","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(91)90170-7","volume":"82","author":"J-J Hebrard","year":"1991","unstructured":"Hebrard, J.-J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theor. Comput. Sci. 82(1), 35\u201349 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"10223_CR28","doi-asserted-by":"crossref","unstructured":"Garel, E.: Minimal separators of two words. In: Proc. CPM 1993. Lecture Notes in Computer Science, vol. 684, pp. 35\u201353 (1993)","DOI":"10.1007\/BFb0029795"},{"key":"10223_CR29","unstructured":"Simon, I.: Words distinguished by their subwords (extended abstract). In: Proc. WORDS 2003. TUCS General Publication, vol. 27, pp. 6\u201313 (2003)"},{"key":"10223_CR30","doi-asserted-by":"crossref","unstructured":"Tron\u00edcek, Z.: Common subsequence automaton. In: Proc. CIAA 2002 (Revised Papers). Lecture Notes in Computer Science, vol. 2608, pp. 270\u2013275 (2002)","DOI":"10.1007\/3-540-44977-9_28"},{"key":"10223_CR31","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Melichar, B., Tron\u00edcek, Z.: Directed acyclic subsequence graph \u2014 overview. J. Discrete Algorithms 1(3\u20134), 255\u2013280 (2003)","DOI":"10.1016\/S1570-8667(03)00029-7"},{"key":"10223_CR32","doi-asserted-by":"crossref","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: Proc. DLT 2020. Lecture Notes in Computer Science, vol. 12086, pp. 14\u201328. Springer (2020)","DOI":"10.1007\/978-3-030-48516-0_2"},{"key":"10223_CR33","doi-asserted-by":"publisher","unstructured":"Day, J.D., Fleischmann, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: The edit distance to $$k$$-subsequence universality. In: 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbr\u00fccken, Germany (Virtual Conference), pp. 25\u201312519 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.25","DOI":"10.4230\/LIPIcs.STACS.2021.25"},{"key":"10223_CR34","unstructured":"Fleischer, L., Kufleitner, M.: Testing Simon\u2019s congruence. In: Proc. MFCS 2018. LIPIcs, vol. 117, pp. 62\u201316213. (2018)"},{"key":"10223_CR35","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\u201313418 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.34","DOI":"10.4230\/LIPIcs.STACS.2021.34"},{"key":"10223_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. Lecture Notes in Computer Science, vol. 13035, pp. 115\u2013131. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-89716-1_8","DOI":"10.1007\/978-3-030-89716-1_8"},{"key":"10223_CR37","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. 367, pp. 11\u201327. (2022). https:\/\/doi.org\/10.4204\/EPTCS.367.2","DOI":"10.4204\/EPTCS.367.2"},{"key":"10223_CR38","unstructured":"Bringmann, K., Chaudhury, B.R.: Sketching, streaming, and fine-grained complexity of (weighted) LCS. In: Proc. FSTTCS 2018. LIPIcs, vol. 122, pp. 40\u201314016. (2018)"},{"key":"10223_CR39","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Multivariate fine-grained complexity of longest common subsequence. In: Proc. SODA 2018, pp. 1216\u20131235. (2018)","DOI":"10.1137\/1.9781611975031.79"},{"key":"10223_CR40","doi-asserted-by":"publisher","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 59\u201378. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.14","DOI":"10.1109\/FOCS.2015.14"},{"key":"10223_CR41","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, V.V., Weimann, O.: Consequences of faster alignment of sequences. In: Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pp. 39\u201351 (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_4","DOI":"10.1007\/978-3-662-43948-7_4"},{"issue":"1","key":"10223_CR42","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."},{"issue":"3","key":"10223_CR43","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. Software Eng. 4(3), 242\u2013254 (1978). https:\/\/doi.org\/10.1109\/TSE.1978.231501","journal-title":"IEEE Trans. Software Eng."},{"issue":"4","key":"10223_CR44","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1016\/j.jcss.2013.11.002","volume":"80","author":"S Buss","year":"2014","unstructured":"Buss, S., Soltys, M.: Unshuffling a square is NP-hard. J. Comput. Syst. Sci. 80(4), 766\u2013776 (2014). https:\/\/doi.org\/10.1016\/j.jcss.2013.11.002","journal-title":"J. Comput. Syst. Sci."},{"key":"10223_CR45","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"},{"issue":"1","key":"10223_CR46","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). https:\/\/doi.org\/10.1007\/s00778-019-00557-w","journal-title":"VLDB J."},{"key":"10223_CR47","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"},{"key":"10223_CR48","doi-asserted-by":"crossref","unstructured":"Li, C., Wang, J.: Efficiently mining closed subsequences with gap constraints. In: SDM, pp. 313\u2013322. SIAM (2008)","DOI":"10.1137\/1.9781611972788.28"},{"issue":"1","key":"10223_CR49","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/2133360.2133362","volume":"6","author":"C Li","year":"2012","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\u20131239 (2012)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"10223_CR50","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. Theor. Comput. Sci. 443, 25\u201334 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.029","journal-title":"Theor. Comput. Sci."},{"key":"10223_CR51","doi-asserted-by":"publisher","unstructured":"Day, J.D., Kosche, M., Manea, F., Schmid, M.L.: Subsequences with gap constraints: Complexity bounds for matching and analysis problems. In: Bae, S.W., Park, H. (eds.) 33rd International Symposium on Algorithms and Computation, ISAAC 2022, December 19-21, 2022, Seoul, Korea. LIPIcs, vol. 248, pp. 64\u201316418. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2022.64","DOI":"10.4230\/LIPIcs.ISAAC.2022.64"},{"key":"10223_CR52","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: 25th International Conference on Database Theory, ICDT 2022. LIPIcs, vol. 220, pp. 18\u201311821. 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":"10223_CR53","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\" (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":"10223_CR54","doi-asserted-by":"publisher","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Pak, V.: Subsequences in bounded ranges: Matching and analysis problems. In: Lin, A.W., Zetzsche, G., Potapov, I. (eds.) Reachability Problems - 16th International Conference, RP 2022, Kaiserslautern, Germany, October 17-21, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13608, pp. 140\u2013159. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-19135-0_10","DOI":"10.1007\/978-3-031-19135-0_10"},{"key":"10223_CR55","unstructured":"Ganardi, M., Hucke, D., K\u00f6nig, D., Lohrey, M., Mamouras, K.: Automata theory on sliding windows. In: STACS. LIPIcs, vol. 96, pp. 31\u201313114. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"10223_CR56","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Querying regular languages over sliding windows. In: FSTTCS. LIPIcs, vol. 65, pp. 18\u201311814. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"10223_CR57","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Randomized sliding window algorithms for regular languages. In: ICALP. LIPIcs, vol. 107, pp. 127\u2013112713. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)","DOI":"10.1007\/978-3-319-77313-1_2"},{"key":"10223_CR58","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Sliding window algorithms for regular languages. In: LATA. Lecture Notes in Computer Science, vol. 10792, pp. 26\u201335. Springer (2018)","DOI":"10.1007\/978-3-319-77313-1_2"},{"key":"10223_CR59","unstructured":"Ganardi, M., Hucke, D., Lohrey, M., Starikovskaya, T.: Sliding window property testing for regular languages. In: ISAAC. LIPIcs, vol. 149, pp. 6\u20131613. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"10223_CR60","doi-asserted-by":"publisher","unstructured":"Abboud, A., Rubinstein, A.: Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. In: 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pp. 35\u201313514 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2018.35","DOI":"10.4230\/LIPIcs.ITCS.2018.35"},{"key":"10223_CR61","doi-asserted-by":"publisher","unstructured":"Iliopoulos, C.S., Kubica, M., Rahman, M.S., Walen, T.: Algorithms for computing the longest parameterized common subsequence. In: Ma, B., Zhang, K. (eds.) Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4580, pp. 265\u2013273. Springer (2007). https:\/\/doi.org\/10.1007\/978-3-540-73437-6_27","DOI":"10.1007\/978-3-540-73437-6_27"},{"key":"10223_CR62","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Gawrychowski, P., Mozes, S., Weimann, O.: An almost optimal edit distance oracle. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference). LIPIcs, vol. 198, pp. 48\u201314820. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.48","DOI":"10.4230\/LIPIcs.ICALP.2021.48"},{"key":"10223_CR63","doi-asserted-by":"publisher","unstructured":"Fredman, M.L., Willard, D.E.: BLASTING through the information theoretic barrier with FUSION TREES. In: Ortiz, H. (ed.) Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pp. 1\u20137. ACM, ??? (1990). https:\/\/doi.org\/10.1145\/100216.100217","DOI":"10.1145\/100216.100217"},{"key":"10223_CR64","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511546853"},{"key":"10223_CR65","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. Lecture Notes in Computer Science, vol. 1776, pp. 88\u201394. Springer (2000). https:\/\/doi.org\/10.1007\/10719839_9","DOI":"10.1007\/10719839_9"},{"key":"10223_CR66","doi-asserted-by":"publisher","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Harrison, M.A., Banerji, R.B., Ullman, J.D. (eds.) Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, pp. 151\u2013158. ACM (1971). https:\/\/doi.org\/10.1145\/800157.805047","DOI":"10.1145\/800157.805047"},{"issue":"2","key":"10223_CR67","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"key":"10223_CR68","doi-asserted-by":"publisher","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians (ICM 2018), pp. 3447\u20133487. World Scientific (2018). https:\/\/doi.org\/10.1142\/9789813272880_0188https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/9789813272880_0188","DOI":"10.1142\/9789813272880_0188"},{"issue":"2\u20133","key":"10223_CR69","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.023","journal-title":"Theor. Comput. Sci."},{"key":"10223_CR70","doi-asserted-by":"crossref","unstructured":"Clifford, P., Clifford, R.: Simple deterministic wildcard matching. Inf. Process. Lett. 101(2), 53\u201354 (2007)","DOI":"10.1016\/j.ipl.2006.08.002"},{"key":"10223_CR71","unstructured":"Manea, F., Richardsen, J., Schmid, M.L.: Subsequences with generalised gap constraints: Upper and lower complexity bounds. Accepted for publication in the Proceedings of CPM 2024. CoRR: to appear. (2024)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10223-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10223-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10223-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T15:22:24Z","timestamp":1767021744000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10223-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":71,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10223"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10223-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"12 April 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"25"}}