{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T19:47:00Z","timestamp":1789674420521,"version":"4.0.1"},"publisher-location":"Cham","reference-count":73,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031191343","type":"print"},{"value":"9783031191350","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-19135-0_10","type":"book-chapter","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T23:03:49Z","timestamp":1665529429000},"page":"140-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Subsequences in\u00a0Bounded Ranges: Matching and\u00a0Analysis Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2165-2695","authenticated-orcid":false,"given":"Maria","family":"Kosche","sequence":"first","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"}]},{"given":"Viktoriya","family":"Pak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,12]]},"reference":[{"key":"10_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 Oct 2015, pp. 59\u201378 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.14","DOI":"10.1109\/FOCS.2015.14"},{"key":"10_CR2","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":"10_CR3","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":"10_CR4","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). https:\/\/doi.org\/10.1016\/0304-3975(91)90358-9","journal-title":"Theor. Comput. Sci."},{"key":"10_CR5","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":"10_CR6","unstructured":"Bathie, G., Starikovskaya, T.: Property testing of regular languages with applications to streaming property testing of visibly pushdown languages. In: ICALP, LIPIcs, vol. 198, pp. 1\u201317. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Baumann, P., Ganardi, M., Thinniyam, R.S., Zetzsche, G.: Existential definability over the subword ordering. In: Berenbrink, P., Monmege, B. (eds.) Proceedings STACS 2022, LIPIcs, vol. 219, pp. 1\u201315 (2022)","DOI":"10.1145\/3498678"},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/s0020-0190(00)00124-1","volume":"76","author":"S Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Segal, M.: Enumerating longest increasing subsequences and patience sorting. Inf. Process. Lett. 76(1), 7\u201311 (2000). https:\/\/doi.org\/10.1016\/s0020-0190(00)00124-1","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10_CR9","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/18M1192226","volume":"33","author":"TC Biedl","year":"2019","unstructured":"Biedl, T.C.: Rollercoasters: long sequences without short runs. SIAM J. Discret. Math. 33(2), 845\u2013861 (2019). https:\/\/doi.org\/10.1137\/18M1192226","journal-title":"SIAM J. Discret. Math."},{"key":"10_CR10","doi-asserted-by":"publisher","unstructured":"Bringmann, K.: Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18\u201321 Oct 2014, pp. 661\u2013670 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.76","DOI":"10.1109\/FOCS.2014.76"},{"key":"10_CR11","doi-asserted-by":"publisher","unstructured":"Bringmann, K.: Fine-grained complexity theory (tutorial). In: 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, 13\u201316 Mar 2019, Berlin, Germany. pp. 1\u20137 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.4","DOI":"10.4230\/LIPIcs.STACS.2019.4"},{"key":"10_CR12","unstructured":"Bringmann, K., Chaudhury, B.R.: Sketching, streaming, and fine-grained complexity of (weighted) LCS. In: Proceedings FSTTCS 2018, LIPIcs, vol. 122, pp. 1\u201316 (2018)"},{"key":"10_CR13","doi-asserted-by":"publisher","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Multivariate fine-grained complexity of longest common subsequence. In: Proceedings SODA 2018, pp. 1216\u20131235 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.79","DOI":"10.1137\/1.9781611975031.79"},{"issue":"4","key":"10_CR14","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":"10_CR15","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings. Cambridge University Press (2007). https:\/\/doi.org\/10.1017\/cbo9780511546853","DOI":"10.1017\/cbo9780511546853"},{"issue":"3\u20134","key":"10_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). https:\/\/doi.org\/10.1016\/s1570-8667(03)00029-7","journal-title":"J. Discrete Algorithms"},{"issue":"9","key":"10_CR17","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.ic.2010.04.003","volume":"208","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Porat, E.: Fast computation of a longest increasing subsequence and application. Inf. Comput. 208(9), 1054\u20131059 (2010). https:\/\/doi.org\/10.1016\/j.ic.2010.04.003","journal-title":"Inf. Comput."},{"key":"10_CR18","unstructured":"Day, J.D., Fleischmann, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: The edit distance to k-subsequence universality. In: Bl\u00e4ser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, 16\u201319 Mar 2021, Saarbr\u00fccken, Germany (Virtual Conference). LIPIcs, vol. 187, pp. 1\u201319. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Day, J.D., Kosche, M., Manea, F., Schmid, M.L.: Subsequences with gap constraints: complexity bounds for matching and analysis problems. arXiv preprint arXiv:2206.13896 (2022)","DOI":"10.1007\/978-3-031-19135-0_10"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-1-4899-3558-8_1","volume":"51","author":"RP Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(1), 161\u2013166 (1950). https:\/\/doi.org\/10.1007\/978-1-4899-3558-8_1","journal-title":"Ann. Math."},{"key":"10_CR21","doi-asserted-by":"publisher","unstructured":"Dudek, B., Gawrychowski, P., Gourdel, G., Starikovskaya, T.: Streaming regular expression membership and pattern matching. In: SODA, pp. 670\u2013694. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.30","DOI":"10.1137\/1.9781611977073.30"},{"key":"10_CR22","unstructured":"Dumitran, M., Gawrychowski, P., Manea, F.: Longest gapped repeats and palindromes. Discret. Math. Theor. Comput. Sci. 19(4) (2017)"},{"key":"10_CR23","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-319-19929-0_14","volume-title":"Combinatorial Pattern Matching","author":"J Fischer","year":"2015","unstructured":"Fischer, J., Gawrychowski, P.: Alphabet-dependent string searching with wexponential search trees. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 160\u2013171. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19929-0_14"},{"key":"10_CR25","unstructured":"Fleischer, L., Kufleitner, M.: Testing Simon\u2019s congruence. In: Proceedings MFCS 2018. LIPIcs, vol. 117, pp. 1\u201313 (2018)"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., Haschke, L., Huch, A., Mayrock, A., Nowotka, D.: Nearly k-universal words - investigating a part of simon\u2019s congruence. arXiv preprint arXiv:2202.07981 (2022)","DOI":"10.1007\/978-3-031-13257-5_5"},{"issue":"1","key":"10_CR27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365x(75)90103-x","volume":"11","author":"ML Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discret. Math. 11(1), 29\u201335 (1975). https:\/\/doi.org\/10.1016\/0012-365x(75)90103-x","journal-title":"Discret. Math."},{"key":"10_CR28","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 (2015). arXiv preprint arXiv:1509.00622"},{"key":"10_CR29","unstructured":"Ganardi, M.: Language recognition in the sliding window model, Ph. D. thesis, University of Siegen, Germany (2019)"},{"key":"10_CR30","unstructured":"Ganardi, M., Hucke, D., K\u00f6nig, D., Lohrey, M., Mamouras, K.: Automata theory on sliding windows. In: STACS, LIPIcs, vol. 96, pp. 1\u201314. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"10_CR31","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Querying regular languages over sliding windows. In: FSTTCS, LIPIcs, vol. 65, pp. 1\u201314. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Randomized sliding window algorithms for regular languages. In: ICALP, LIPIcs, vol. 107, pp. 1\u201313. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)","DOI":"10.1007\/978-3-319-77313-1_2"},{"key":"10_CR33","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":"10_CR34","unstructured":"Ganardi, M., Hucke, D., Lohrey, M., Starikovskaya, T.: Sliding window property testing for regular languages. In: ISAAC, LIPIcs, vol. 149, pp. 1\u201313. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"10_CR35","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":"10_CR36","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 Mar 2021, Saarbr\u00fccken, Germany (Virtual Conference), pp. 1\u201318 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.34","DOI":"10.4230\/LIPIcs.STACS.2021.34"},{"issue":"4","key":"10_CR37","doi-asserted-by":"publisher","first-page":"1081","DOI":"10.1007\/s00453-021-00908-6","volume":"84","author":"P Gawrychowski","year":"2022","unstructured":"Gawrychowski, P., Manea, F., Serafin, R.: Fast and Longest Rollercoasters. Algorithmica 84(4), 1081\u20131106 (2022). https:\/\/doi.org\/10.1007\/s00453-021-00908-6","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR38","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":"10_CR39","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 LICS 2017, pp. 1\u201312 (2017). https:\/\/doi.org\/10.1109\/lics.2017.8005141","DOI":"10.1109\/lics.2017.8005141"},{"key":"10_CR40","doi-asserted-by":"crossref","unstructured":"Hebrard, J.J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theor. Comput. Sci. 82(1), 35\u201349 (1991)","DOI":"10.1016\/0304-3975(91)90170-7"},{"key":"10_CR41","doi-asserted-by":"publisher","unstructured":"Heged\u00fcs, L., Nagy, B.: On periodic properties of circular words. Discrete Math. 339, 1189\u20131197 (2016). https:\/\/doi.org\/10.1016\/j.disc.2015.10.043","DOI":"10.1016\/j.disc.2015.10.043"},{"issue":"5","key":"10_CR42","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 common subsequences. Commun. ACM 20(5), 350\u2013353 (1977). https:\/\/doi.org\/10.1145\/359581.359603","journal-title":"Commun. ACM"},{"issue":"2","key":"10_CR43","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."},{"issue":"4","key":"10_CR44","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","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","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10_CR45","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). https:\/\/doi.org\/10.1016\/j.ipl.2014.11.008","journal-title":"Inf. Process. Lett."},{"key":"10_CR46","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages with applications in logical complexity. In: Proceedings CSL 2016, LIPIcs, vol. 62, pp. 1\u201322 (2016)"},{"key":"10_CR47","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)"},{"issue":"6","key":"10_CR48","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006). https:\/\/doi.org\/10.1145\/1217856.1217858","journal-title":"J. ACM"},{"key":"10_CR49","doi-asserted-by":"crossref","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Pak, V.: Subsequences in bounded ranges: matching and analysis problems. arXiv preprint arXiv:2207.09201 (2022)","DOI":"10.1007\/978-3-031-19135-0_10"},{"key":"10_CR50","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":"10_CR51","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":"10_CR52","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":"10_CR53","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":"10_CR54","doi-asserted-by":"crossref","unstructured":"Leroy, J., Rigo, M., Stipulanti, M.: Generalized Pascal triangle for binomial coefficients of words. Electron. J. Combin. 24, 36\u201344 (2017)","DOI":"10.37236\/6581"},{"key":"10_CR55","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":"10_CR56","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). https:\/\/doi.org\/10.1145\/322063.322075","journal-title":"J. ACM"},{"key":"10_CR57","doi-asserted-by":"publisher","unstructured":"Manea, F., Tiseanu, C.: The hardness of counting full words compatible with partial words. J. Comput. Syst. Sci. 79(1), 7\u201322 (2013). https:\/\/doi.org\/10.1016\/j.jcss.2012.04.001","DOI":"10.1016\/j.jcss.2012.04.001"},{"issue":"1","key":"10_CR58","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."},{"key":"10_CR59","doi-asserted-by":"publisher","unstructured":"Pin, J.-E.: The consequences of Imre simon\u2019s work in the theory of automata, languages, and semigroups. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, p. 5. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24698-5_4","DOI":"10.1007\/978-3-540-24698-5_4"},{"issue":"1","key":"10_CR60","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":"10_CR61","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":"10_CR62","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). https:\/\/doi.org\/10.1016\/j.tcs.2015.07.025","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10_CR63","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). https:\/\/doi.org\/10.1016\/j.tcs.2005.03.024","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR64","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). https:\/\/doi.org\/10.1016\/j.tcs.2011.10.017","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10_CR65","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."},{"key":"10_CR66","unstructured":"Simon, I.: Hierarchies of events with dot-depth one, Ph. D. thesis, University of Waterloo (1972)"},{"key":"10_CR67","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":"10_CR68","unstructured":"Simon, I.: Words distinguished by their subwords (extended abstract). In: Proceedings WORDS 2003. TUCS General Publication, vol. 27, pp. 6\u201313 (2003)"},{"key":"10_CR69","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":"10_CR70","doi-asserted-by":"publisher","unstructured":"Williams, V.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, 16\u201318 Sept 2015, Patras, Greece, pp. 17\u201329 (2015). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2015.17","DOI":"10.4230\/LIPIcs.IPEC.2015.17"},{"key":"10_CR71","unstructured":"Zetzsche, G.: The complexity of downward closure comparisons. In: Proceedings ICALP 2016. LIPIcs, vol. 55, pp. 1\u201314 (2016)"},{"key":"10_CR72","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"},{"key":"10_CR73","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, 29 March to 1 April 2022, Edinburgh, UK (Virtual Conference). LIPIcs, vol. 220, pp. 1\u201321. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2022.18","DOI":"10.4230\/LIPIcs.ICDT.2022.18"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-19135-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,7]],"date-time":"2023-03-07T22:58:07Z","timestamp":1678229887000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-19135-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031191343","9783031191350"],"references-count":73,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-19135-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"12 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kaiserslautern","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/rp2022.mpi-sws.org\/","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":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"14","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":"8","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":"57% - 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":"3","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":"No","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 talks are also included.","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)"}}]}}