{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:52Z","timestamp":1778807752522,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T00:00:00Z","timestamp":1581379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>\n            A pattern \u0251 (i.e., a string of variables and terminals) matches a word\n            <jats:italic>w<\/jats:italic>\n            , if\n            <jats:italic>w<\/jats:italic>\n            can be obtained by uniformly replacing the variables of \u0251 by terminal words. The respective matching problem, i.e., deciding whether or not a given pattern matches a given word, is generally NP-complete, but can be solved in polynomial-time for restricted classes of patterns. We present efficient algorithms for the matching problem with respect to patterns with a bounded number of repeated variables and patterns with a structural restriction on the order of variables. Furthermore, we show that it is NP-complete to decide, for a given number\n            <jats:italic>k<\/jats:italic>\n            and a word\n            <jats:italic>w<\/jats:italic>\n            , whether\n            <jats:italic>w<\/jats:italic>\n            can be factorised into\n            <jats:italic>k<\/jats:italic>\n            distinct factors. As an immediate consequence of this hardness result, the injective version (i.e., different variables are replaced by different words) of the matching problem is NP-complete even for very restricted classes of patterns.\n          <\/jats:p>","DOI":"10.1145\/3369935","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T12:28:17Z","timestamp":1582633697000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Pattern Matching with Variables"],"prefix":"10.1145","volume":"12","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[{"name":"Fachbereich IV\u2013Abteilung Informatikwissenschaften, Universit\u00e4t Trier, Trier, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florin","family":"Manea","sequence":"additional","affiliation":[{"name":"G\u00f6ttingen University, Institute of Computer Science, Goettingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Merca\u015f","sequence":"additional","affiliation":[{"name":"Loughborough University, Department of Computer Science, Leicestershire, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[{"name":"Fachbereich IV\u2013Abteilung Informatikwissenschaften, Universit\u00e4t Trier, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.10.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90041-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118400014"},{"key":"e_1_2_1_5_1","volume-title":"Wood","author":"Barcel\u00f3 Pablo","year":"2012","unstructured":"Pablo Barcel\u00f3 , Leonid Libkin , Anthony W. Lin , and Peter T . Wood . 2012 . Expressive languages for path queries over graph-structured data. ACM Trans. Database Syst . 37 (2012). Pablo Barcel\u00f3, Leonid Libkin, Anthony W. Lin, and Peter T. Wood. 2012. Expressive languages for path queries over graph-structured data. ACM Trans. Database Syst. 37 (2012)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410300214X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_29"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_27"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2014.11.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90024-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90073-B"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190846"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00136-5"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","author":"Fernau Henning","unstructured":"Henning Fernau , Florin Manea , Robert Mercas , and Markus L. Schmid . 2015. Pattern matching with variables: Fast algorithms and new hardness results . In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915) . 302--315. Henning Fernau, Florin Manea, Robert Mercas, and Markus L. Schmid. 2015. Pattern matching with variables: Fast algorithms and new hardness results. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915). 302--315."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.04.035"},{"key":"e_1_2_1_16_1","first-page":"287","article-title":"Pattern matching with variables: A multivariate complexity analysis. Info","volume":"242","author":"Fernau Henning","year":"2015","unstructured":"Henning Fernau and Markus L. Schmid . 2015 . Pattern matching with variables: A multivariate complexity analysis. Info . Comput. 242 (2015), 287 -- 305 . Henning Fernau and Markus L. Schmid. 2015. Pattern matching with variables: A multivariate complexity analysis. Info. Comput. 242 (2015), 287--305.","journal-title":"Comput."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Henning Fernau Markus L. Schmid and Yngve Villanger. 2015. On the parameterised complexity of string morphism problems. Theory Comput. Syst. (2015).  Henning Fernau Markus L. Schmid and Yngve Villanger. 2015. On the parameterised complexity of string morphism problems. Theory Comput. Syst. (2015).","DOI":"10.1007\/s00224-015-9635-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9389-0"},{"key":"e_1_2_1_19_1","volume-title":"Mastering Regular Expressions","author":"Friedl Jeffrey E. F.","unstructured":"Jeffrey E. F. Friedl . 2006. Mastering Regular Expressions ( 3 rd ed.). O\u2019Reilly , Sebastopol, CA . Jeffrey E. F. Friedl. 2006. Mastering Regular Expressions (3rd ed.). O\u2019Reilly, Sebastopol, CA.","edition":"3"},{"key":"e_1_2_1_20_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY."},{"key":"e_1_2_1_21_1","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"Gusfield Dan","unstructured":"Dan Gusfield . 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology . Cambridge University Press , New York, NY . Dan Gusfield. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(94)00091-G"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337255"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2nd Annual Workshop on Computational Learning Theory (COLT\u201989)","author":"Michael","unstructured":"Michael J. Kearns and Leonard Pitt. 1989. A polynomial-time algorithm for learning k-variable pattern languages from examples . In Proceedings of the 2nd Annual Workshop on Computational Learning Theory (COLT\u201989) . 57--71. Michael J. Kearns and Leonard Pitt. 1989. A polynomial-time algorithm for learning k-variable pattern languages from examples. In Proceedings of the 2nd Annual Workshop on Computational Learning Theory (COLT\u201989). 57--71."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_30"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.36"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_22"},{"key":"e_1_2_1_29_1","volume-title":"Combinatorics on Words","author":"Lothaire M.","unstructured":"M. Lothaire . 1997. Combinatorics on Words . Cambridge University Press . M. Lothaire. 1997. Combinatorics on Words. Cambridge University Press."},{"key":"e_1_2_1_30_1","volume-title":"Algebraic Combinatorics on Words","author":"Lothaire M.","unstructured":"M. Lothaire . 2002. Algebraic Combinatorics on Words . Cambridge University Press , Cambridge\/ New York . M. Lothaire. 2002. Algebraic Combinatorics on Words. Cambridge University Press, Cambridge\/New York."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1994283-402331"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.028"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0008-8"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.029"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 15th International Conference on Implementation and Application of Automata (CIAA\u201910)","author":"Reidenbach Daniel","unstructured":"Daniel Reidenbach and Markus L. Schmid . 2010. A polynomial time match test for large classes of extended regular expressions . In Proceedings of the 15th International Conference on Implementation and Application of Automata (CIAA\u201910) . 241--250. Daniel Reidenbach and Markus L. Schmid. 2010. A polynomial time match test for large classes of extended regular expressions. In Proceedings of the 15th International Conference on Implementation and Application of Automata (CIAA\u201910). 241--250."},{"key":"e_1_2_1_36_1","first-page":"87","article-title":"Patterns with bounded treewidth. Info","volume":"239","author":"Reidenbach Daniel","year":"2014","unstructured":"Daniel Reidenbach and Markus L. Schmid . 2014 . Patterns with bounded treewidth. Info . Comput. 239 (2014), 87 -- 99 . Daniel Reidenbach and Markus L. Schmid. 2014. Patterns with bounded treewidth. Info. Comput. 239 (2014), 87--99.","journal-title":"Comput."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.06.011"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.01.006"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science (MFCS\u201982)","author":"Shinohara Takeshi","year":"1982","unstructured":"Takeshi Shinohara . 1982 . Polynomial time inference of pattern languages and its application . In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science (MFCS\u201982) . 191--209. Takeshi Shinohara. 1982. Polynomial time inference of pattern languages and its application. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science (MFCS\u201982). 191--209."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369935","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369935","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:27Z","timestamp":1750203867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369935"}},"subtitle":["Efficient Algorithms and Complexity Results"],"short-title":[],"issued":{"date-parts":[[2020,2,11]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3369935"],"URL":"https:\/\/doi.org\/10.1145\/3369935","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,11]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}