{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T02:11:34Z","timestamp":1792807894881,"version":"4.5.0"},"publisher-location":"Cham","reference-count":68,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031452857","type":"print"},{"value":"9783031452864","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-45286-4_12","type":"book-chapter","created":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T05:02:28Z","timestamp":1696395748000},"page":"155-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Matching Patterns with\u00a0Variables Under Simon\u2019s Congruence"],"prefix":"10.1007","author":[{"given":"Pamela","family":"Fleischmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sungmin","family":"Kim","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":"Dirk","family":"Nowotka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Siemer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Max","family":"Wiedenh\u00f6ft","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,10,5]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Adamson, D.: Ranking and unranking $$k$$-subsequence universal words. In: Frid, A., Merca\u015f, R. (eds.) Combinatorics on Words, WORDS 2023. LNCS, vol. 13899, pp. 47\u201359. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-33180-0_4","DOI":"10.1007\/978-3-031-33180-0_4"},{"key":"12_CR2","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., Merca\u015f, R. (eds.) Combinatorics on Words. WORDS 2023. Lecture Notes in Computer Science, vol. 13899, pp. 60\u201376. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-33180-0_5","DOI":"10.1007\/978-3-031-33180-0_5"},{"issue":"1","key":"12_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3484198","volume":"55","author":"R Amadini","year":"2021","unstructured":"Amadini, R.: A survey on string constraint solving. ACM Comput. Surv. (CSUR) 55(1), 1\u201338 (2021)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jda.2006.10.001","volume":"5","author":"A Amir","year":"2007","unstructured":"Amir, A., Nor, I.: Generalized function matching. J. Discrete Algorithms 5, 514\u2013523 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"12_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21(1), 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR6","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":"12_CR7","first-page":"758","volume":"49","author":"NG de Bruijn","year":"1946","unstructured":"de Bruijn, N.G.: A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758\u2013764 (1946)","journal-title":"Koninklijke Nederlandse Akademie v. Wetenschappen"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1142\/S012905410300214X","volume":"14","author":"C C\u00e2mpeanu","year":"2003","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci. 14, 1007\u20131018 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.endm.2017.06.043","volume":"61","author":"HZQ Chen","year":"2017","unstructured":"Chen, H.Z.Q., Kitaev, S., M\u00fctze, T., Sun, B.Y.: On universal partial words. Electron. Notes Discrete Math. 61, 231\u2013237 (2017)","journal-title":"Electron. Notes Discrete Math."},{"key":"12_CR10","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":"12_CR11","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":"12_CR12","unstructured":"Day, J., Fleischmann, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: The edit distance to k-subsequence universality. In: STACS, vol. 187, pp. 25:1\u201325:19 (2021)"},{"key":"12_CR13","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D.: Local patterns. In: Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017. LIPIcs, vol. 93, pp. 24:1\u201324:14 (2017)"},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Fagin, R., Kimelfeld, B., Reiss, F., Vansummeren, S.: Document spanners: a formal approach to information extraction. J. ACM 62(2), 12:1\u201312:51 (2015)","DOI":"10.1145\/2699442"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.tcs.2018.04.035","volume":"733","author":"H Fernau","year":"2018","unstructured":"Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Revisiting Shinohara\u2019s algorithm for computing descriptive patterns. Theor. Comput. Sci. 733, 44\u201354 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Pattern matching with variables: efficient algorithms and complexity results. ACM Trans. Comput. Theor. 12(1), 6:1\u20136:37 (2020)","DOI":"10.1145\/3369935"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.ic.2015.03.006","volume":"242","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: a multivariate complexity analysis. Inf. Comput. 242, 287\u2013305 (2015)","journal-title":"Inf. Comput."},{"issue":"1","key":"12_CR19","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s00224-015-9635-3","volume":"59","author":"H Fernau","year":"2016","unstructured":"Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. Theor. Comput. Syst. 59(1), 24\u201351 (2016)","journal-title":"Theor. Comput. Syst."},{"key":"12_CR20","unstructured":"Fleischer, L., Kufleitner, M.: Testing Simon\u2019s congruence. In: Potapov, I., Spirakis, P.G., Worrell, J. (eds.) MFCS 2018. LIPIcs, vol. 117, pp. 62:1\u201362:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"12_CR21","unstructured":"Fleischmann, P., Germann, S., Nowotka, D.: Scattered factor universality-the power of the remainder. preprint arXiv:2104.09063 (published at RuFiDim) (2021)"},{"key":"12_CR22","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 (2023)","DOI":"10.1007\/978-3-031-43587-4_14"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., et al.: Matching patterns with variables under Simon\u2019s congruence (2023)","DOI":"10.1007\/978-3-031-45286-4_12"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00224-012-9389-0","volume":"53","author":"DD Freydenberger","year":"2013","unstructured":"Freydenberger, D.D.: Extended regular expressions: succinctness and decidability. Theor. Comput. Syst. 53, 159\u2013193 (2013)","journal-title":"Theor. Comput. Syst."},{"issue":"7","key":"12_CR25","doi-asserted-by":"publisher","first-page":"1679","DOI":"10.1007\/s00224-018-9874-1","volume":"63","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D.: A logic for document spanners. Theor. Comput. Syst. 63(7), 1679\u20131754 (2019)","journal-title":"Theor. Comput. Syst."},{"key":"12_CR26","unstructured":"Freydenberger, D.D., Gawrychowski, P., Karhum\u00e4ki, J., Manea, F., Rytter, W.: Testing k-binomial equivalence. CoRR abs\/1509.00622 (2015)"},{"issue":"4","key":"12_CR27","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1007\/s00224-017-9770-0","volume":"62","author":"DD Freydenberger","year":"2018","unstructured":"Freydenberger, D.D., Holldack, M.: Document spanners: from expressive power to decision problems. Theor. Comput. Syst. 62(4), 854\u2013898 (2018)","journal-title":"Theor. Comput. Syst."},{"key":"12_CR28","unstructured":"Freydenberger, D.D., Peterfreund, L.: The theory of concatenation over finite models. In: Bansal, N., Merelli, E., Worrell, J. (eds.) ICALP 2021, Proceedings. LIPIcs, vol. 198, pp. 130:1\u2013130:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2019.04.001","volume":"105","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D., Schmid, M.L.: Deterministic regular expressions with back-references. J. Comput. Syst. Sci. 105, 1\u201339 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR30","volume-title":"Mastering Regular Expressions","author":"JEF Friedl","year":"2006","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions, 3rd edn. O\u2019Reilly, Sebastopol, CA (2006)","edition":"3"},{"key":"12_CR31","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":"12_CR32","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)"},{"key":"12_CR33","unstructured":"Gawrychowski, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Efficiently testing Simon\u2019s congruence. In: STACS 2021. LIPIcs, vol. 187, pp. 34:1\u201334:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"12_CR34","unstructured":"Gawrychowski, P., Lange, M., Rampersad, N., Shallit, J.O., Szykula, M.: Existential length universality. In: Proceedings of the STACS 2020. LIPIcs, vol. 154, pp. 16:1\u201316:14 (2020)"},{"key":"12_CR35","unstructured":"Gawrychowski, P., Manea, F., Siemer, S.: Matching patterns with variables under Hamming distance. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021. LIPIcs, vol. 202, pp. 48:1\u201348:24 (2021)"},{"key":"12_CR36","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Manea, F., Siemer, S.: Matching patterns with variables under edit distance. In: Arroyuelo, D., Poblete, B. (eds.) String Processing and Information Retrieval, SPIRE 2022. LNCS, vol. 13617, pp. 275\u2013289. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-20643-6_20","DOI":"10.1007\/978-3-031-20643-6_20"},{"key":"12_CR37","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2017.12.022","volume":"713","author":"B Goeckner","year":"2018","unstructured":"Goeckner, B., et al.: Universal partial words over non-binary alphabets. Theor. Comput. Sci. 713, 56\u201365 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"12_CR38","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/3373394.3373396","volume":"6","author":"M Hague","year":"2019","unstructured":"Hague, M.: Strings at MOSCA. ACM SIGLOG News 6(4), 4\u201322 (2019)","journal-title":"ACM SIGLOG News"},{"issue":"1","key":"12_CR39","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(91)90170-7","volume":"82","author":"J H\u00e9brard","year":"1991","unstructured":"H\u00e9brard, J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theoret. Comput. Sci. 82(1), 35\u201349 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR40","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages with applications in logical complexity. In: CSL (2016)"},{"issue":"8","key":"12_CR41","doi-asserted-by":"publisher","first-page":"2189","DOI":"10.1016\/j.jcta.2013.08.008","volume":"120","author":"J Karhum\u00e4ki","year":"2013","unstructured":"Karhum\u00e4ki, J., Saarela, A., Zamboni, L.Q.: On a generalization of Abelian equivalence and complexity of infinite words. J. Comb. Theor. Ser. A 120(8), 2189\u20132206 (2013)","journal-title":"J. Comb. Theor. Ser. A"},{"issue":"1","key":"12_CR42","doi-asserted-by":"publisher","first-page":"175","DOI":"10.14232\/actacyb.23.1.2017.11","volume":"23","author":"J Karhum\u00e4ki","year":"2017","unstructured":"Karhum\u00e4ki, J., Saarela, A., Zamboni, L.Q.: Variations of the Morse-Hedlund theorem for k-abelian equivalence. Acta Cybern. 23(1), 175\u2013189 (2017)","journal-title":"Acta Cybern."},{"key":"12_CR43","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"12_CR44","unstructured":"Kim, S., Ko, S., Han, Y.: Simon\u2019s congruence pattern matching. 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. 60:1\u201360:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"12_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-031-13257-5_10","volume-title":"Descriptional Complexity of Formal Systems","author":"S Kim","year":"2022","unstructured":"Kim, S., Han, Y.S., Ko, S.K., Salomaa, K.: On Simon\u2019s congruence closure of a string. In: Han, Y.S., Vaszil, G. (eds.) DCFS 2022. LNCS, vol. 13439, pp. 127\u2013141. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-13257-5_10"},{"key":"12_CR46","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 (2022)"},{"key":"12_CR47","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":"12_CR48","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, vol. 367, pp. 11\u201327 (2022)","DOI":"10.4204\/EPTCS.367.2"},{"key":"12_CR49","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.ic.2017.06.004","volume":"255","author":"M Kr\u00f6tzsch","year":"2017","unstructured":"Kr\u00f6tzsch, M., Masopust, T., Thomazo, M.: Complexity of universality and related problems for partially ordered NFAs. Inf. Comput. 255, 177\u2013192 (2017)","journal-title":"Inf. Comput."},{"issue":"07","key":"12_CR50","doi-asserted-by":"publisher","first-page":"1375","DOI":"10.1142\/S0218196720500459","volume":"30","author":"M Lejeune","year":"2020","unstructured":"Lejeune, M., Rigo, M., Rosenfeld, M.: The binomial equivalence classes of finite words. Int. J. Algebra Comput. 30(07), 1375\u20131397 (2020)","journal-title":"Int. J. Algebra Comput."},{"key":"12_CR51","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Combinatorics on Words. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511566097"},{"key":"12_CR52","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press (2002)","DOI":"10.1017\/CBO9781107326019"},{"issue":"12","key":"12_CR53","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1090\/S0002-9904-1934-05988-3","volume":"40","author":"MH Martin","year":"1934","unstructured":"Martin, M.H.: A problem in arrangements. Bull. Am. Math. Soc. 40(12), 859\u2013864 (1934)","journal-title":"Bull. Am. Math. Soc."},{"issue":"1\u20134","key":"12_CR54","first-page":"223","volume":"116","author":"N Rampersad","year":"2012","unstructured":"Rampersad, N., Shallit, J., Xu, Z.: The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages. Fundam. Inf. 116(1\u20134), 223\u2013236 (2012)","journal-title":"Fundam. Inf."},{"key":"12_CR55","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.ic.2014.08.010","volume":"239","author":"D Reidenbach","year":"2014","unstructured":"Reidenbach, D., Schmid, M.L.: Patterns with bounded treewidth. Inf. Comput. 239, 87\u201399 (2014). https:\/\/doi.org\/10.1016\/j.ic.2014.08.010","journal-title":"Inf. Comput."},{"key":"12_CR56","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":"19","key":"12_CR57","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1016\/j.ipl.2013.06.011","volume":"113","author":"ML Schmid","year":"2013","unstructured":"Schmid, M.L.: A note on the complexity of matching patterns with variables. Inf. Process. Lett. 113(19), 729\u2013733 (2013)","journal-title":"Inf. Process. Lett."},{"key":"12_CR58","unstructured":"Schmid, M.L., Schweikardt, N.: A purely regular approach to non-regular core spanners. In: Proceedings of the 24th International Conference on Database Theory, ICDT 2021. LIPIcs, vol. 186, pp. 4:1\u20134:19 (2021)"},{"key":"12_CR59","doi-asserted-by":"crossref","unstructured":"Schmid, M.L., Schweikardt, N.: Document spanners - a brief overview of concepts, results, and recent developments. In: International Conference on Management of Data, PODS 2022, pp. 139\u2013150. ACM (2022)","DOI":"10.1145\/3517804.3526069"},{"key":"12_CR60","unstructured":"Schnoebelen, P., Karandikar, P.: The height of piecewise-testable languages and the complexity of the logic of subwords. Logical Meth. Comput. Sci. 15, 6:1\u20136:27 (2019)"},{"key":"12_CR61","doi-asserted-by":"publisher","unstructured":"Schnoebelen, P., Veron, J.: On arch factorization and subword universality for words and compressed words. In: Frid, A., Merca\u015f, R. (eds.) Combinatorics on Words, WORDS 2023. LNCS, vol. 13899, pp. 274\u2013287. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-031-33180-0_21","DOI":"10.1007\/978-3-031-33180-0_21"},{"key":"12_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/3-540-12920-0_29","volume-title":"STACS 84","author":"KP Jantke","year":"1984","unstructured":"Jantke, K.P.: Polynomial time inference of general pattern languages. In: Fontet, M., Mehlhorn, K. (eds.) STACS 1984. LNCS, vol. 166, pp. 314\u2013325. Springer, Heidelberg (1984). https:\/\/doi.org\/10.1007\/3-540-12920-0_29"},{"key":"12_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-60217-8_13","volume-title":"Algorithmic Learning for Knowledge-Based Systems","author":"T Shinohara","year":"1995","unstructured":"Shinohara, T., Arikawa, S.: Pattern inference. In: Jantke, K.P., Lange, S. (eds.) Algorithmic Learning for Knowledge-Based Systems. LNCS, vol. 961, pp. 259\u2013291. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60217-8_13"},{"key":"12_CR64","unstructured":"Simon, I.: Hierarchies of events with dot-depth one. Ph.D. thesis, University of Waterloo (1972)"},{"key":"12_CR65","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":"12_CR66","unstructured":"Simon, I.: Words distinguished by their subwords (extended abstract). In: Proceedings of the WORDS 2003, vol. 27, pp. 6\u201313. TUCS General Publication (2003)"},{"key":"12_CR67","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"},{"issue":"3","key":"12_CR68","first-page":"1","volume":"5","author":"P Weis","year":"2009","unstructured":"Weis, P., Immerman, N.: Structure theorem and strict alternation hierarchy for FO$$^2$$ on words. Log. Meth. Comput. Sci. 5(3), 1\u201323 (2009)","journal-title":"Log. Meth. Comput. Sci."}],"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-45286-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,23]],"date-time":"2023-12-23T04:19:45Z","timestamp":1703305185000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-45286-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031452857","9783031452864"],"references-count":68,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-45286-4_12","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":"5 October 2023","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":"Nice","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":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 October 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 October 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.lix.polytechnique.fr\/Labo\/Olivier.Bournez\/RP2023\/i.php?n=Main.Home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair.org","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","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":"13","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":"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":"4","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)"}}]}}