{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T19:47:02Z","timestamp":1789674422313,"version":"4.0.1"},"publisher-location":"Cham","reference-count":62,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031331794","type":"print"},{"value":"9783031331800","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-33180-0_5","type":"book-chapter","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T23:03:27Z","timestamp":1685487807000},"page":"60-76","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Longest Common Subsequence with\u00a0Gap Constraints"],"prefix":"10.1007","author":[{"given":"Duncan","family":"Adamson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maria","family":"Kosche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tore","family":"Ko\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florin","family":"Manea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Siemer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,5,31]]},"reference":[{"key":"5_CR1","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\u201320 October 2015, pp. 59\u201378. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.14","DOI":"10.1109\/FOCS.2015.14"},{"key":"5_CR2","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, 11\u201314 January 2018, Cambridge, MA, USA, pp. 35:1\u201335:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2018.35","DOI":"10.4230\/LIPIcs.ITCS.2018.35"},{"key":"5_CR3","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, 8\u201311 July 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"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Adamson, D., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Longest common subsequence with gap constraints. arXiv e-prints arXiv:2304.05270 (2023)","DOI":"10.1007\/978-3-031-33180-0_5"},{"key":"5_CR5","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, 19\u201323 June 2017, pp. 7\u201310 (2017). https:\/\/doi.org\/10.1145\/3093742.3095106","DOI":"10.1145\/3093742.3095106"},{"issue":"2","key":"5_CR6","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":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-030-48516-0_2","volume-title":"Developments in Language Theory","author":"L Barker","year":"2020","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: Jonoska, N., Savchuk, D. (eds.) DLT 2020. LNCS, vol. 12086, pp. 14\u201328. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-48516-0_2"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: de la Fuente, P. (ed.) Seventh International Symposium on String Processing and Information Retrieval, SPIRE 2000, A Coru\u00f1a, Spain, 27\u201329 September 2000, pp. 39\u201348. IEEE Computer Society (2000). https:\/\/doi.org\/10.1109\/SPIRE.2000.878178","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"5_CR10","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":"5_CR11","unstructured":"Bringmann, K., Chaudhury, B.R.: Sketching, streaming, and fine-grained complexity of (weighted) LCS. In: Proceedings FSTTCS 2018. LIPIcs, vol. 122, pp. 40:1\u201340:16 (2018)"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Multivariate fine-grained complexity of longest common subsequence. In: Proceedings of SODA 2018, pp. 1216\u20131235 (2018)","DOI":"10.1137\/1.9781611975031.79"},{"key":"5_CR13","doi-asserted-by":"publisher","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","DOI":"10.1016\/j.jcss.2013.11.002"},{"key":"5_CR14","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, 12\u201316 July 2021, Glasgow, Scotland (Virtual Conference). LIPIcs, vol. 198, pp. 48:1\u201348:20. 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":"5_CR15","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Sankoff, D.: Longest common subsequences of two random sequences. J. Appli. Probability 12(2), 306\u2013315 (1975). http:\/\/www.jstor.org\/stable\/3212444","DOI":"10.2307\/3212444"},{"issue":"3\u20134","key":"5_CR16","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\u00edcek, Z.: Directed acyclic subsequence graph \u2013 overview. J. Discrete Algorithms 1(3\u20134), 255\u2013280 (2003)","journal-title":"J. Discrete Algorithms"},{"key":"5_CR17","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, 16\u201319 March 2021, Saarbr\u00fccken, Germany (Virtual Conference), pp. 25:1\u201325:19 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.25","DOI":"10.4230\/LIPIcs.STACS.2021.25"},{"key":"5_CR18","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, 19\u201321 December 2022, Seoul, Korea. LIPIcs, vol. 248, pp. 64:1\u201364:18. 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":"5_CR19","unstructured":"Fleischer, L., Kufleitner, M.: Testing Simon\u2019s congruence. In: Proceedings of MFCS 2018. LIPIcs, vol. 117, pp. 62:1\u201362:13 (2018)"},{"key":"5_CR20","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. P\u0103un 65th birthday, pp. 239\u2013248, available in CoRR abs\/ arXiv: 1509.00622 (2015)"},{"key":"5_CR21","unstructured":"Ganardi, M., Hucke, D., K\u00f6nig, D., Lohrey, M., Mamouras, K.: Automata theory on sliding windows. In: STACS. LIPIcs, vol. 96, pp. 31:1\u201331:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Querying regular languages over sliding windows. In: FSTTCS. LIPIcs, , vol. 65, pp. 18:1\u201318:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)","DOI":"10.1007\/s00224-020-10000-1"},{"key":"5_CR23","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Randomized sliding window algorithms for regular languages. In: ICALP. LIPIcs, vol. 107, pp. 127:1\u2013127:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-319-77313-1_2","volume-title":"Language and Automata Theory and Applications","author":"M Ganardi","year":"2018","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Sliding window algorithms for regular languages. In: Klein, S.T., Mart\u00edn-Vide, C., Shapira, D. (eds.) LATA 2018. LNCS, vol. 10792, pp. 26\u201335. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-77313-1_2"},{"key":"5_CR25","unstructured":"Ganardi, M., Hucke, D., Lohrey, M., Starikovskaya, T.: Sliding window property testing for regular languages. In: ISAAC. LIPIcs, vol. 149, pp. 6:1\u20136:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BFb0029795","volume-title":"Combinatorial Pattern Matching","author":"E Garel","year":"1993","unstructured":"Garel, E.: Minimal separators of two words. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1993. LNCS, vol. 684, pp. 35\u201353. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/BFb0029795"},{"key":"5_CR27","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, 16\u201319 March 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"},{"issue":"1","key":"5_CR28","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00778-019-00557-w","volume":"29","author":"N Giatrakos","year":"2019","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 (2019). https:\/\/doi.org\/10.1007\/s00778-019-00557-w","journal-title":"VLDB J."},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Halfon, S., Schnoebelen, P., Zetzsche, G.: Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In: Proceedings LICS 2017, pp. 1\u201312 (2017)","DOI":"10.1109\/LICS.2017.8005141"},{"issue":"1","key":"5_CR30","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(91)90170-7","volume":"82","author":"JJ 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":"5_CR31","doi-asserted-by":"publisher","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","DOI":"10.1145\/322033.322044"},{"key":"5_CR32","doi-asserted-by":"publisher","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","DOI":"10.1145\/359581.359603"},{"key":"5_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-540-73437-6_27","volume-title":"Combinatorial Pattern Matching","author":"CS Iliopoulos","year":"2007","unstructured":"Iliopoulos, C.S., Kubica, M., Rahman, M.S., Wale\u0144, T.: Algorithms for computing the longest parameterized common subsequence. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 265\u2013273. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73437-6_27"},{"issue":"4","key":"5_CR34","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":"5_CR35","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages with applications in logical complexity. In: Proceedings CSL 2016. LIPIcs, vol. 62, pp. 37:1\u201337:22 (2016)"},{"key":"5_CR36","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)"},{"key":"5_CR37","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: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":"5_CR38","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":"5_CR39","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, 17\u201321 October 2022, Proceedings. LNCS, 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":"5_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-030-89716-1_8","volume-title":"Reachability Problems","author":"M Kosche","year":"2021","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Absent subsequences in words. In: Bell, P.C., Totzke, P., Potapov, I. (eds.) RP 2021. LNCS, vol. 13035, pp. 115\u2013131. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-89716-1_8"},{"key":"5_CR41","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, 26\u201327 August 2022. EPTCS, vol. 367, pp. 11\u201327 (2022). https:\/\/doi.org\/10.4204\/EPTCS.367.2","DOI":"10.4204\/EPTCS.367.2"},{"key":"5_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-030-50026-9_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"D Kuske","year":"2020","unstructured":"Kuske, D.: The subtrace order and counting first-order logic. In: Fernau, H. (ed.) CSR 2020. LNCS, vol. 12159, pp. 289\u2013302. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-50026-9_21"},{"key":"5_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-030-17127-8_20","volume-title":"Foundations of Software Science and Computation Structures","author":"D Kuske","year":"2019","unstructured":"Kuske, D., Zetzsche, G.: Languages ordered by the subword order. In: Boja\u0144czyk, M., Simpson, A. (eds.) FoSSaCS 2019. LNCS, vol. 11425, pp. 348\u2013364. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17127-8_20"},{"key":"5_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-030-24886-4_21","volume-title":"Developments in Language Theory","author":"M Lejeune","year":"2019","unstructured":"Lejeune, M., Leroy, J., Rigo, M.: Computing the k-binomial complexity of the thue\u2013morse word. In: Hofman, P., Skrzypczak, M. (eds.) DLT 2019. LNCS, vol. 11647, pp. 278\u2013291. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-24886-4_21"},{"key":"5_CR45","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":"5_CR46","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"},{"key":"5_CR47","doi-asserted-by":"crossref","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)","DOI":"10.1145\/2133360.2133362"},{"issue":"2","key":"5_CR48","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"},{"key":"5_CR49","doi-asserted-by":"publisher","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","DOI":"10.1016\/0022-0000(80)90002-1"},{"issue":"1","key":"5_CR50","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."},{"key":"5_CR51","doi-asserted-by":"publisher","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","DOI":"10.1007\/BF00264437"},{"key":"5_CR52","doi-asserted-by":"publisher","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","DOI":"10.1016\/0096-0551(79)90009-2"},{"key":"5_CR53","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."},{"issue":"2","key":"5_CR54","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":"5_CR55","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."},{"key":"5_CR56","doi-asserted-by":"publisher","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","DOI":"10.1109\/TSE.1978.231501"},{"key":"5_CR57","unstructured":"Simon, I.: Hierarchies of events with dot-depth one \u2013 Ph.D. thesis. University of Waterloo (1972)"},{"key":"5_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/3-540-07407-4_23","volume-title":"Automata Theory and Formal Languages","author":"I Simon","year":"1975","unstructured":"Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 214\u2013222. Springer, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07407-4_23"},{"key":"5_CR59","unstructured":"Simon, I.: Words distinguished by their subwords (extended abstract). In: Proceedings of WORDS 2003, vol. 27, pp. 6\u201313. TUCS General Publication (2003)"},{"key":"5_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-44977-9_28","volume-title":"Implementation and Application of Automata","author":"Z Troni\u0109ek","year":"2003","unstructured":"Troni\u0109ek, Z.: Common subsequence automaton. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 270\u2013275. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44977-9_28"},{"key":"5_CR61","unstructured":"Zetzsche, G.: The complexity of downward closure comparisons. In: Proceedings of ICALP 2016. LIPIcs, vol. 55, pp. 123:1\u2013123:14 (2016)"},{"key":"5_CR62","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, 22\u201327 June 2014, pp. 217\u2013228 (2014). https:\/\/doi.org\/10.1145\/2588555.2593671","DOI":"10.1145\/2588555.2593671"}],"container-title":["Lecture Notes in Computer Science","Combinatorics on Words"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-33180-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T12:41:11Z","timestamp":1702557671000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-33180-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031331794","9783031331800"],"references-count":62,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-33180-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"31 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WORDS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorics on Words","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ume\u00e5","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sweden","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cwords2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dltwords2023.cs.umu.se\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 Invited papers included in this proceedings","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}