{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T22:29:12Z","timestamp":1791412152939,"version":"4.3.3"},"publisher-location":"Cham","reference-count":83,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030287955","type":"print"},{"value":"9783030287962","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-28796-2_1","type":"book-chapter","created":{"date-parts":[[2019,9,1]],"date-time":"2019-09-01T23:02:43Z","timestamp":1567378963000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Matching Patterns with Variables"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,8,9]]},"reference":[{"key":"1_CR1","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"},{"key":"1_CR2","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, 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"BS Baker","year":"1996","unstructured":"Baker, B.S.: Parameterized pattern matching: algorithms and applications. J. Comput. Syst. Sci. 52, 28\u201342 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"1_CR4","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/15M1011032","volume":"46","author":"Hideo Bannai","year":"2017","unstructured":"Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\u201d theorem. SIAM J. Comput. 46(5), 1501\u20131514 (2017)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/2389241.2389250","volume":"37","author":"P Barcel\u00f3","year":"2012","unstructured":"Barcel\u00f3, P., Libkin, L., Lin, A.W., Wood, P.T.: Expressive languages for path queries over graph-structured data. ACM Trans. Database Syst. 37, 31 (2012)","journal-title":"ACM Trans. Database Syst."},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-22110-1_14","volume-title":"Computer Aided Verification","author":"C Barrett","year":"2011","unstructured":"Barrett, C., et al.: CVC4. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 171\u2013177. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22110-1_14"},{"issue":"1\u20132","key":"1_CR7","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"issue":"5","key":"1_CR8","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/s0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(5), 1305\u20131317 (1996). https:\/\/doi.org\/10.1137\/s0097539793251219","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"1_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theor. Comput. Sci."},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-30891-8_12","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L.: Fixed-parameter tractability of treewidth and pathwidth. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 196\u2013227. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30891-8_12"},{"key":"1_CR11","doi-asserted-by":"publisher","unstructured":"Bringmann, K.: Fine-grained complexity theory (tutorial). In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 126, pp. 4:1\u20134:7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.4. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10243","DOI":"10.4230\/LIPIcs.STACS.2019.4"},{"key":"1_CR12","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":"1_CR13","unstructured":"Casel, K., Day, J.D., Fleischmann, P., Kociumaka, T., Manea, F., Schmid, M.L.: Graph and string parameters: connections between pathwidth, cutwidth and the locality number. CoRR, to appear in Proceedings of the ICALP 2019, abs\/1902.10983 (2019). http:\/\/arxiv.org\/abs\/1902.10983"},{"issue":"5","key":"1_CR14","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(81)90024-7","volume":"12","author":"M Crochemore","year":"1981","unstructured":"Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett. 12(5), 244\u2013250 (1981)","journal-title":"Inf. Process. Lett."},{"key":"1_CR15","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D.: Local patterns. In: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, pp. 24:1\u201324:14 (2017)"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-319-98654-8_22","volume-title":"Developments in Language Theory","author":"JD Day","year":"2018","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D., Schmid, M.L.: On matching generalised repetitive patterns. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 269\u2013281. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_22"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-030-00250-3_2","volume-title":"Reachability Problems","author":"JD Day","year":"2018","unstructured":"Day, J.D., Ganesh, V., He, P., Manea, F., Nowotka, D.: The satisfiability of word equations: decidable and undecidable theories. In: Potapov, I., Reynier, P.-A. (eds.) RP 2018. LNCS, vol. 11123, pp. 15\u201329. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00250-3_2"},{"key":"1_CR18","unstructured":"Day, J.D., Manea, F., Nowotka, D.: The hardness of solving simple word equations. In: Proceedings of the MFCS 2017. LIPIcs, vol. 83, pp. 18:1\u201318:14 (2017)"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-540-27836-8_36","volume-title":"Automata, Languages and Programming","author":"R Da\u0327browski","year":"2004","unstructured":"Da\u0327browski, R., Plandowski, W.: Solving two-variable word equations. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 408\u2013419. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27836-8_36"},{"issue":"3","key":"1_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313\u2013356 (2002). https:\/\/doi.org\/10.1145\/568522.568523","journal-title":"ACM Comput. Surv."},{"key":"1_CR21","unstructured":"Diekert, V., Jez, A., Kufleitner, M.: Solutions of word equations over partially commutative structures. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pp. 127:1\u2013127:14 (2016)"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-49116-3_20","volume-title":"STACS 99","author":"JM Robson","year":"1999","unstructured":"Robson, J.M., Diekert, V.: On quadratic word equations. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 217\u2013226. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_20"},{"key":"1_CR23","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. TCS. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0304-3975(00)00136-5","volume":"261","author":"T Erlebach","year":"2001","unstructured":"Erlebach, T., Rossmanith, P., Stadtherr, H., Steger, A., Zeugmann, T.: Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. Theoret. Comput. Sci. 261, 119\u2013156 (2001)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1_CR25","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299x","volume":"38","author":"U Feige","year":"2008","unstructured":"Feige, U., HajiAghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629\u2013657 (2008). https:\/\/doi.org\/10.1137\/05064299x","journal-title":"SIAM J. Comput."},{"key":"1_CR26","unstructured":"Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Pattern matching with variables: fast algorithms and new hardness results. In: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, pp. 302\u2013315 (2015)"},{"key":"1_CR27","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. Theoret. Comput. Sci. 733, 44\u201354 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-38905-4_10","volume-title":"Combinatorial Pattern Matching","author":"H Fernau","year":"2013","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: a multivariate complexity analysis. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 83\u201394. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38905-4_10"},{"key":"1_CR29","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."},{"key":"1_CR30","unstructured":"Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. In: Proceedings of the 33rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS. Leibniz International Proceedings in Informatics (LIPIcs), vol. 24, pp. 55\u201366 (2013)"},{"issue":"1","key":"1_CR31","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. Theory Comput. Syst. 59(1), 24\u201351 (2016)","journal-title":"Theory Comput. Syst."},{"key":"1_CR32","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. TTCSAES. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"key":"1_CR33","unstructured":"Freydenberger, D.D.: A logic for document spanners. In: Proceedings of the 20th International Conference on Database Theory, ICDT 2017. Leibniz International Proceedings in Informatics (LIPIcs)"},{"issue":"4","key":"1_CR34","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. Theory Comput. Syst. 62(4), 854\u2013898 (2018)","journal-title":"Theory Comput. Syst."},{"key":"1_CR35","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. Theory Comput. Syst. 53, 159\u2013193 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"1_CR36","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.ic.2009.04.002","volume":"208","author":"DD Freydenberger","year":"2010","unstructured":"Freydenberger, D.D., Reidenbach, D.: Bad news on decision problems for patterns. Inf. Comput. 208(1), 83\u201396 (2010)","journal-title":"Inf. Comput."},{"issue":"34\u201336","key":"1_CR37","doi-asserted-by":"publisher","first-page":"3274","DOI":"10.1016\/j.tcs.2010.05.033","volume":"411","author":"DD Freydenberger","year":"2010","unstructured":"Freydenberger, D.D., Reidenbach, D.: Existence and nonexistence of descriptive patterns. Theor. Comput. Sci. 411(34\u201336), 3274\u20133286 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1_CR38","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1016\/j.jcss.2012.10.001","volume":"79","author":"DD Freydenberger","year":"2013","unstructured":"Freydenberger, D.D., Reidenbach, D.: Inferring descriptive generalisations of formal languages. J. Comput. Syst. Sci. 79(5), 622\u2013639 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR39","volume-title":"Mastering Regular Expressions","author":"JEF Friedl","year":"2006","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions, 3rd edn. O\u2019Reilly, Sebastopol (2006)","edition":"3"},{"key":"1_CR40","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 (1979)"},{"key":"1_CR41","unstructured":"Gawrychowski, P., Manea, F., Nowotka, D.: Testing generalised freeness of words. In: STACS 2014. LIPIcs, vol. 25, pp. 337\u2013349. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)"},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., I, T., Inenaga, S., K\u00f6ppl, D., Manea, F.: Tighter bounds and optimal algorithms for all maximal $$\\alpha $$-gapped repeats and palindromes - finding all maximal $$\\alpha $$-gapped repeats and palindromes in optimal worst case time on integer alphabets. Theory Comput. Syst. 62(1), 162\u2013191 (2018)","DOI":"10.1007\/s00224-017-9794-5"},{"key":"1_CR43","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.jcss.2018.10.004","volume":"101","author":"Pawe\u0142 Gawrychowski","year":"2019","unstructured":"Gawrychowski, P., Manea, F., Mercas, R., Nowotka, D.: Hide and seek with repetitions. J. Comput. Syst. Sci. 101, 42\u201367 (2019). https:\/\/doi.org\/10.1016\/j.jcss.2018.10.004","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR44","unstructured":"Gawrychowski, P., Manea, F., Mercas, R., Nowotka, D., Tiseanu, C.: Finding pseudo-repetitions. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, 27 February-2 March 2013. LIPIcs, vol. 20, pp. 257\u2013268 (2013)"},{"key":"1_CR45","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-24412-4_10","volume-title":"Algorithmic Learning Theory","author":"M Geilke","year":"2011","unstructured":"Geilke, M., Zilles, S.: Learning relational patterns. In: Kivinen, J., Szepesv\u00e1ri, C., Ukkonen, E., Zeugmann, T. (eds.) ALT 2011. LNCS (LNAI), vol. 6925, pp. 84\u201398. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-24412-4_10"},{"key":"1_CR46","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 of the 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, pp. 1\u201312. IEEE Computer Society (2017)","DOI":"10.1109\/LICS.2017.8005141"},{"key":"1_CR47","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0167-8655(94)00091-G","volume":"16","author":"OH Ibarra","year":"1995","unstructured":"Ibarra, O.H., Pong, T.C., Sohn, S.M.: A note on parsing pattern languages. Pattern Recogn. Lett. 16, 179\u2013182 (1995)","journal-title":"Pattern Recogn. Lett."},{"issue":"1","key":"1_CR48","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/78935.78938","volume":"37","author":"J Jaffar","year":"1990","unstructured":"Jaffar, J.: Minimal and complete word unification. J. ACM 37(1), 47\u201385 (1990)","journal-title":"J. ACM"},{"key":"1_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-662-43951-7_21","volume-title":"Automata, Languages, and Programming","author":"A Je\u017c","year":"2014","unstructured":"Je\u017c, A.: Context unification is in PSPACE. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 244\u2013255. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_21"},{"key":"1_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-014-9931-3","volume":"74","author":"A Je\u017c","year":"2016","unstructured":"Je\u017c, A.: One-variable word equations in linear time. Algorithmica 74, 1\u201348 (2016)","journal-title":"Algorithmica"},{"key":"1_CR51","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2743014","volume":"63","author":"A Je\u017c","year":"2016","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. J. ACM 63, 4 (2016)","journal-title":"J. ACM"},{"issue":"1","key":"1_CR52","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1006\/jcss.1995.1006","volume":"50","author":"T Jiang","year":"1995","unstructured":"Jiang, T., Salomaa, A., Salomaa, K., Yu, S.: Decision problems for patterns. J. Comput. Syst. Sci. 50(1), 53\u201363 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR53","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/337244.337255","volume":"47","author":"J Karhum\u00e4ki","year":"2000","unstructured":"Karhum\u00e4ki, J., Plandowski, W., Mignosi, F.: The expressibility of languages and relations by word equations. J. ACM 47, 483\u2013505 (2000)","journal-title":"J. ACM"},{"key":"1_CR54","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, 918\u2013936 (2006)","journal-title":"J. ACM"},{"key":"1_CR55","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Pitt, L.: A polynomial-time algorithm for learning k-variable pattern languages from examples. In: Proceedings of the Second Annual Workshop on Computational Learning Theory, COLT 1989, Santa Cruz, CA, USA, 31 July\u20132 August 1989, pp. 57\u201371 (1989)","DOI":"10.1016\/B978-0-08-094829-4.50007-6"},{"key":"1_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","year":"1994","unstructured":"Kloks, T. (ed.): Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0045375"},{"issue":"51","key":"1_CR57","doi-asserted-by":"publisher","first-page":"5365","DOI":"10.1016\/j.tcs.2009.09.013","volume":"410","author":"R Kolpakov","year":"2009","unstructured":"Kolpakov, R., Kucherov, G.: Searching for gapped palindromes. Theor. Comput. Sci. 410(51), 5365\u20135373 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-319-07566-2_22","volume-title":"Combinatorial Pattern Matching","author":"R Kolpakov","year":"2014","unstructured":"Kolpakov, R., Podolskiy, M., Posypkin, M., Khrapov, N.: Searching of gapped repeats and subrepetitions in a word. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 212\u2013221. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_22"},{"key":"1_CR59","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-319-67428-5_22","volume-title":"String Processing and Information Retrieval","author":"Dmitry Kosolobov","year":"2017","unstructured":"Kosolobov, D., Manea, F., Nowotka, D.: Detecting one-variable patterns. In: Proceedings of the 24th International Symposium on String Processing and Information Retrieval , SPIRE 2017, Palermo, Italy, 26\u201329 September 2017, pp. 254\u2013270 (2017)"},{"issue":"6","key":"1_CR60","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787\u2013832 (1999). https:\/\/doi.org\/10.1145\/331524.331526","journal-title":"J. ACM"},{"key":"1_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/978-3-030-01090-4_21","volume-title":"Automated Technology for Verification and Analysis","author":"AW Lin","year":"2018","unstructured":"Lin, A.W., Majumdar, R.: Quadratic word equations with length constraints, counter systems, and presburger arithmetic with divisibility. In: Lahiri, S.K., Wang, C. (eds.) ATVA 2018. LNCS, vol. 11138, pp. 352\u2013369. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-01090-4_21"},{"key":"1_CR62","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on Words","author":"M Lothaire","year":"1997","unstructured":"Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge (1997)"},{"key":"1_CR63","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words, chap. 3. Cambridge University Press, Cambridge, New York (2002)","DOI":"10.1017\/CBO9781107326019"},{"key":"1_CR64","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, New York (2002)"},{"key":"1_CR65","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1090\/S0002-9947-1960-0151503-8","volume":"96","author":"RC Lyndon","year":"1960","unstructured":"Lyndon, R.C.: Equations in free groups. Trans. Am. Math. Soc. 96, 445\u2013457 (1960)","journal-title":"Trans. Am. Math. Soc."},{"key":"1_CR66","volume-title":"Combinatorial Group Theory","author":"RC Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer, Heidelberg (1977)"},{"key":"1_CR67","first-page":"147","volume":"103","author":"GS Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Matematicheskii Sbornik 103, 147\u2013236 (1977)","journal-title":"Matematicheskii Sbornik"},{"key":"1_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-662-53132-7_25","volume-title":"Developments in Language Theory","author":"F Manea","year":"2016","unstructured":"Manea, F., Nowotka, D., Schmid, M.L.: On the solvability problem for restricted classes of word equations. In: Brlek, S., Reutenauer, C. (eds.) DLT 2016. LNCS, vol. 9840, pp. 306\u2013318. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53132-7_25"},{"key":"1_CR69","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1051\/ita\/1994283-402331","volume":"28","author":"A Mateescu","year":"1994","unstructured":"Mateescu, A., Salomaa, A.: Finite degrees of ambiguity in pattern languages. RAIRO Inf. Th\u00e9or. Appl. 28, 233\u2013253 (1994)","journal-title":"RAIRO Inf. Th\u00e9or. Appl."},{"key":"1_CR70","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-642-59136-5_4","volume-title":"Handbook of Formal Languages","author":"A Mateescu","year":"1997","unstructured":"Mateescu, A., Salomaa, A.: Aspects of classical language theory. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 175\u2013251. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_4"},{"key":"1_CR71","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.tcs.2008.02.028","volume":"397","author":"YK Ng","year":"2008","unstructured":"Ng, Y.K., Shinohara, T.: Developments from enquiries into the learnability of the pattern languages from positive data. Theoret. Comput. Sci. 397, 150\u2013165 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR72","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-015-0008-8","volume":"75","author":"S Ordyniak","year":"2016","unstructured":"Ordyniak, S., Popa, A.: A parameterized study of maximum generalized pattern matching problems. Algorithmica 75, 1\u201326 (2016)","journal-title":"Algorithmica"},{"key":"1_CR73","unstructured":"Petit, J.: Addenda to the survey of layout problems. Bull. EATCS 105, 177\u2013201 (2011). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/98"},{"key":"1_CR74","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: An efficient algorithm for solving word equations. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 467\u2013476 (2006)","DOI":"10.1145\/1132516.1132584"},{"issue":"1","key":"1_CR75","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2005.10.017","volume":"350","author":"D Reidenbach","year":"2006","unstructured":"Reidenbach, D.: A non-learnable class of e-pattern languages. Theor. Comput. Sci. 350(1), 91\u2013102 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1_CR76","first-page":"407","volume":"12","author":"D Reidenbach","year":"2007","unstructured":"Reidenbach, D.: An examination of ohlebusch and ukkonen\u2019s conjecture on the equivalence problem for e-pattern languages. J. Automata Lang. Comb. 12(3), 407\u2013426 (2007)","journal-title":"J. Automata Lang. Comb."},{"issue":"1\u20133","key":"1_CR77","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.tcs.2008.02.029","volume":"397","author":"D Reidenbach","year":"2008","unstructured":"Reidenbach, D.: Discontinuities in pattern inference. Theor. Comput. Sci. 397(1\u20133), 166\u2013193 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR78","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)","journal-title":"Inf. Comput."},{"issue":"19\u201321","key":"1_CR79","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\u201321), 729\u2013733 (2013)","journal-title":"Inf. Process. Lett."},{"key":"1_CR80","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF00881904","volume":"11","author":"KU Schulz","year":"1995","unstructured":"Schulz, K.U.: Word unification and transformation of generalized equations. J. Autom. Reason. 11, 149\u2013184 (1995)","journal-title":"J. Autom. Reason."},{"key":"1_CR81","unstructured":"Shinohara, T.: Polynomial time inference of pattern languages and its application. In: Proceedings of 7th IBM Symposium on Mathematical Foundations of Computer Science, MFCS, pp. 191\u2013209 (1982)"},{"issue":"1","key":"1_CR82","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth I: a linear time fixed parameter algorithm. J. Algorithms 56(1), 1\u201324 (2005). https:\/\/doi.org\/10.1016\/j.jalgor.2004.12.001","journal-title":"J. Algorithms"},{"issue":"2\u20133","key":"1_CR83","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10703-016-0263-6","volume":"50","author":"Y Zheng","year":"2017","unstructured":"Zheng, Y., Ganesh, V., Subramanian, S., Tripp, O., Berzish, M., Dolby, J., Zhang, X.: Z3str2: an efficient solver for strings, regular expressions, and length constraints. Formal Methods Syst. Des. 50(2\u20133), 249\u2013288 (2017)","journal-title":"Formal Methods Syst. Des."}],"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-030-28796-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T13:17:44Z","timestamp":1710249464000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-28796-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030287955","9783030287962"],"references-count":83,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-28796-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"9 August 2019","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":"Loughborough","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cwords2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/words2019.lboro.ac.uk\/","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":"34","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":"21","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":"62% - 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":"7","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)"}}]}}