{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T19:46:58Z","timestamp":1789674418136,"version":"4.0.1"},"publisher-location":"Singapore","reference-count":63,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819683116","type":"print"},{"value":"9789819683123","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-8312-3_2","type":"book-chapter","created":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T07:55:34Z","timestamp":1751270134000},"page":"16-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["k-Universality of\u00a0Regular Languages Revisited"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3343-2435","authenticated-orcid":false,"given":"Duncan","family":"Adamson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1531-7970","authenticated-orcid":false,"given":"Pamela","family":"Fleischmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1145-5806","authenticated-orcid":false,"given":"Annika","family":"Huch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6002-1581","authenticated-orcid":false,"given":"Tore","family":"Ko\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,6,30]]},"reference":[{"key":"2_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\u201320 October 2015, pp. 59\u201378 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.14","DOI":"10.1109\/FOCS.2015.14"},{"key":"2_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":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-662-43948-7_4","volume-title":"Automata, Languages, and Programming","author":"A Abboud","year":"2014","unstructured":"Abboud, A., Williams, V.V., Weimann, O.: Consequences of faster alignment of sequences. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 39\u201351. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_4"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Adamson, D.: Ranking and unranking $$k$$-subsequence universal words. In: Frid, A., Merca\u015f, R. (eds.) WORDS, pp. 47\u201359. Springer (2023)","DOI":"10.1007\/978-3-031-33180-0_4"},{"key":"2_CR5","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Ko\u00df, T., Manea, F., Nowotka, D.: k-universality of regular languages. In: ISAAC 2023. LIPIcs, vol.\u00a0283, pp. 4:1\u20134:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Adamson, D., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Longest common subsequence with gap constraints. In: Frid, A., Merca\u015f, R. (eds.) WORDS, pp. 60\u201376 (2023)","DOI":"10.1007\/978-3-031-33180-0_5"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/11821069_10","volume-title":"Mathematical Foundations of Computer Science 2006","author":"C Allauzen","year":"2006","unstructured":"Allauzen, C., Mohri, M.: A unified construction of the glushkov, follow, and antimirov automata. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 110\u2013121. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11821069_10"},{"key":"2_CR8","doi-asserted-by":"publisher","unstructured":"Anand, A., Zetzsche, G.: Priority downward closures. In: P\u00e9rez, G.A., Raskin, J. (eds.) 34th International Conference on Concurrency Theory, CONCUR 2023, 18\u201323 September 2023, Antwerp, Belgium. LIPIcs, vol.\u00a0279, pp. 39:1\u201339:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.CONCUR.2023.39","DOI":"10.4230\/LIPICS.CONCUR.2023.39"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Artikis, A., Margara, A., Ugarte, M., Vansummeren, S., Weidlich, M.: Complex event recognition languages: tutorial. In: DEBS, pp. 7\u201310 (2017)","DOI":"10.1145\/3093742.3095106"},{"issue":"2","key":"2_CR10","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":"2_CR11","doi-asserted-by":"crossref","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: DLT, pp. 14\u201328. Springer (2020)","DOI":"10.1007\/978-3-030-48516-0_2"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: SPIRE, pp. 39\u201348. IEEE Computer Society (2000)","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"2_CR13","doi-asserted-by":"publisher","unstructured":"Bringmann, K., Chaudhury, B.R.: Sketching, streaming, and fine-grained complexity of (weighted) LCS. In: Ganguly, S., Pandya, P. (eds.) 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). LIPIcs, vol.\u00a0122, pp. 40:1\u201340:16 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2018.40","DOI":"10.4230\/LIPIcs.FSTTCS.2018.40"},{"key":"2_CR14","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"},{"issue":"2","key":"2_CR15","doi-asserted-by":"publisher","first-page":"306","DOI":"10.2307\/3212444","volume":"12","author":"V Chvatal","year":"1975","unstructured":"Chvatal, V., Sankoff, D.: Longest common subsequences of two random sequences. J. Appl. Probab. 12(2), 306\u2013315 (1975)","journal-title":"J. Appl. Probab."},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511546853"},{"issue":"3\u20134","key":"2_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\u00edcek, Z.: Directed acyclic subsequence graph - overview. J. Discrete Algorithms 1(3\u20134), 255\u2013280 (2003)","journal-title":"J. Discrete Algorithms"},{"key":"2_CR18","unstructured":"Day, J., Fleischmann, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: The edit distance to k-subsequence universality. In: STACS, vol.\u00a0187, pp. 25:1\u201325:19 (2021)"},{"key":"2_CR19","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.\u00a0248, 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":"2_CR20","unstructured":"Fazekas, S.Z., Ko\u00df, T., Manea, F., Merca\u015f, R., Specht, T.: Subsequence matching and analysis problems for formal languages (2024). https:\/\/arxiv.org\/abs\/2410.07992"},{"key":"2_CR21","unstructured":"Fleischer, L., Kufleitner, M.: Testing simon\u2019s congruence. In: MFCS. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"2_CR22","unstructured":"Fleischmann, P., Germann, S., Nowotka, D.: Scattered factor universality\u2013the power of the remainder. preprint arXiv:2104.09063 (published at RuFiDim) (2021)"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., H\u00f6fer, J., Huch, A., Nowotka, D.: $$\\alpha $$-$$\\beta $$-factorization and the binary case of simon\u2019s congruence. In: FCT. LNCS, vol. 14292, pp. 190\u2013204. Springer (2023)","DOI":"10.1007\/978-3-031-43587-4_14"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., Kim, S., Ko\u00df, T., Manea, F., Nowotka, D., Siemer, S., Wiedenh\u00f6ft, M.: Matching patterns with variables under simon\u2019s congruence. In: RP 2023. LNCS, vol. 14235, pp. 155\u2013170. Springer (2023)","DOI":"10.1007\/978-3-031-45286-4_12"},{"key":"2_CR25","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, 13\u201317 May 1990, Baltimore, Maryland, USA, pp.\u00a01\u20137. ACM (1990). https:\/\/doi.org\/10.1145\/100216.100217","DOI":"10.1145\/100216.100217"},{"key":"2_CR26","unstructured":"Frochaux, A., Kleest-Mei\u00dfner, S.: Puzzling over subsequence-query extensions: disjunction and generalised gaps. In: AMW 2023. CEUR Workshop Proceedings, vol.\u00a03409. CEUR-WS.org (2023)"},{"key":"2_CR27","unstructured":"Gawrychowski, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Efficiently testing simon\u2019s congruence. In: STACS, vol.\u00a0187, pp. 34:1\u201334:18 (2021)"},{"key":"2_CR28","doi-asserted-by":"publisher","unstructured":"Gruber, H., Holzer, M.: From finite automata to regular expressions and back - a summary on descriptional complexity. Int. J. Found. Comput. Sci. 26(8), 1009\u20131040 (2015). https:\/\/doi.org\/10.1142\/S0129054115400110","DOI":"10.1142\/S0129054115400110"},{"key":"2_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: LICS, pp. 1\u201312. IEEE (2017)","DOI":"10.1109\/LICS.2017.8005141"},{"issue":"5","key":"2_CR30","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1093\/bioinformatics\/btz742","volume":"36","author":"R Han","year":"2020","unstructured":"Han, R., Wang, S., Gao, X.: Novel algorithms for efficient subsequence searching and mapping in nanopore raw signals towards targeted sequencing. Bioinformatics 36(5), 1333\u20131343 (2020)","journal-title":"Bioinformatics"},{"issue":"1","key":"2_CR31","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. TCS 82(1), 35\u201349 (1991)","journal-title":"TCS"},{"issue":"1","key":"2_CR32","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"3","author":"G Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 3(1), 326\u2013336 (1952)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"4","key":"2_CR33","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)","journal-title":"J. ACM"},{"key":"2_CR34","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)"},{"key":"2_CR35","doi-asserted-by":"publisher","unstructured":"Hopcroft, J.E., Karp, R.M.: An n$$ ^{\\text{5\/2}}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","DOI":"10.1137\/0202019"},{"issue":"5","key":"2_CR36","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)","journal-title":"Commun. ACM"},{"key":"2_CR37","doi-asserted-by":"publisher","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/JCSS.2001.1774","DOI":"10.1006\/JCSS.2001.1774"},{"issue":"4","key":"2_CR38","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":"2_CR39","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages with applications in logical complexity. In: CSL (2016)"},{"key":"2_CR40","unstructured":"Kim, S., Ko, S., Han, Y.: Simon\u2019s congruence pattern matching. In: ISAAC. LIPIcs, vol.\u00a0248, pp. 60:1\u201360:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"2_CR41","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. LIPIcs, vol.\u00a0220, pp. 18:1\u201318:21 (2022)"},{"key":"2_CR42","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. LNI, vol. P-331, pp. 511\u2013533 (2023)"},{"key":"2_CR43","doi-asserted-by":"crossref","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Absent subsequences in words. In: RP, pp. 115\u2013131. Springer (2021)","DOI":"10.1007\/978-3-030-89716-1_8"},{"key":"2_CR44","doi-asserted-by":"crossref","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.) NCMA (2022)","DOI":"10.4204\/EPTCS.367.2"},{"key":"2_CR45","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-031-19135-0_10","volume-title":"Reachability Problems","author":"M Kosche","year":"2022","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.) RP 2022. LNCS, vol. 13608, pp. 140\u2013159. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-19135-0_10"},{"key":"2_CR46","doi-asserted-by":"crossref","unstructured":"Kuske, D.: The subtrace order and counting first-order logic. In: CSR. LNCS, vol. 12159, pp. 289\u2013302. Springer (2020)","DOI":"10.1007\/978-3-030-50026-9_21"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Kuske, D., Zetzsche, G.: Languages ordered by the subword order. In: FOSSACS. LNCS, vol. 11425, pp. 348\u2013364. Springer (2019)","DOI":"10.1007\/978-3-030-17127-8_20"},{"key":"2_CR48","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/92"},{"issue":"2","key":"2_CR49","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":"2_CR50","doi-asserted-by":"publisher","unstructured":"Manea, F., Richardsen, J., Schmid, M.L.: Subsequences with generalised gap constraints: upper and lower complexity bounds. In: Inenaga, S., Puglisi, S.J. (eds.) 35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024, 25\u201327 June 2024, Fukuoka, Japan. LIPIcs, vol.\u00a0296, pp. 22:1\u201322:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2024.22","DOI":"10.4230\/LIPICS.CPM.2024.22"},{"key":"2_CR51","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"},{"key":"2_CR52","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)","journal-title":"Acta Informatica"},{"key":"2_CR53","doi-asserted-by":"crossref","unstructured":"Schnoebelen, P., Karandikar, P.: The height of piecewise-testable languages and the complexity of the logic of subwords. Log. Methods Comput. Sci. 15 (2019)","DOI":"10.23638\/LMCS-15(2:6)2019"},{"key":"2_CR54","doi-asserted-by":"crossref","unstructured":"Schnoebelen, P., Veron, J.: On arch factorization and subword universality for words and compressed words. In: WORDS. LNCS, vol. 13899, pp. 274\u2013287. Springer (2023)","DOI":"10.1007\/978-3-031-33180-0_21"},{"key":"2_CR55","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1109\/TSE.1978.231501","volume":"3","author":"AC Shaw","year":"1978","unstructured":"Shaw, A.C.: Software descriptions with flow expressions. IEEE Trans. Software Eng. 3, 242\u2013254 (1978)","journal-title":"IEEE Trans. Software Eng."},{"key":"2_CR56","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13104-019-4256-6","volume":"12","author":"R Shikder","year":"2019","unstructured":"Shikder, R., Thulasiraman, P., Irani, P., Hu, P.: An openmp-based tool for finding longest common subsequence in bioinformatics. BMC. Res. Notes 12, 1\u20136 (2019)","journal-title":"BMC. Res. Notes"},{"key":"2_CR57","unstructured":"Simon, I.: Hierarchies of events with dot-depth one. Ph.D. thesis, University of Waterloo, Department of Applied Analysis and Computer Science (1972)"},{"key":"2_CR58","doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages, 2nd GI Conference. LNCS, vol.\u00a033, pp. 214\u2013222. Springer (1975)","DOI":"10.1007\/3-540-07407-4_23"},{"key":"2_CR59","first-page":"6","volume":"27","author":"I Simon","year":"2003","unstructured":"Simon, I.: Words distinguished by their subwords. WORDS 27, 6\u201313 (2003)","journal-title":"WORDS"},{"key":"2_CR60","doi-asserted-by":"publisher","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972). https:\/\/doi.org\/10.1137\/0201010","DOI":"10.1137\/0201010"},{"key":"2_CR61","doi-asserted-by":"crossref","unstructured":"Troni\u0109ek, Z.: Common subsequence automaton. In: CIAA, pp. 270\u2013275 (2003)","DOI":"10.1007\/3-540-44977-9_28"},{"key":"2_CR62","unstructured":"Zetzsche, G.: The complexity of downward closure comparisons. In: ICALP, vol.\u00a055, pp. 123:1\u2013123:14 (2016)"},{"key":"2_CR63","doi-asserted-by":"crossref","unstructured":"Zetzsche, G.: Separability by piecewise testable languages and downward closures beyond subwords. In: LICS 2018, pp. 929\u2013938. ACM (2018)","DOI":"10.1145\/3209108.3209201"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-8312-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T17:40:49Z","timestamp":1789580449000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-8312-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819683116","9789819683123"],"references-count":63,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-8312-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"30 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJTCS-FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"faw2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ijtcs-faw.github.io\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}