{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T03:59:02Z","timestamp":1790049542423,"version":"4.0.1"},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"8","license":[{"start":{"date-parts":[[2018,8,2]],"date-time":"2018-08-02T00:00:00Z","timestamp":1533168000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p>We consider term rewriting under sharing in the form of compression by singleton tree grammars (STG), which is more general than the term dags. Algorithms for the subtasks of rewriting are analysed: finding a redex for rewriting by locating a position for a match, performing a rewrite step by constructing the compressed result and executing a sequence of rewrite steps. The first main result is that locating a match of a linear term<jats:italic>s<\/jats:italic>in another term<jats:italic>t<\/jats:italic>can be performed in polynomial time if<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>are both STG-compressed. This generalizes results on matching of STG-compressed terms, matching of straight-line-program-compressed strings with character-variables, where every variable occurs at most once, and on fully compressed matching of strings. Also, for the case where<jats:italic>s<\/jats:italic>is directed-acyclic-graph (DAG)-compressed, it is shown that submatching can be performed in polynomial time. The general case of compressed submatching can be computed in non-deterministic polynomial time, and an algorithm is described that may be exponential in the worst case, its complexity is<jats:italic>n<\/jats:italic><jats:sup><jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>)<\/jats:sup>, where<jats:italic>k<\/jats:italic>is the number of variables with double occurrences in<jats:italic>s<\/jats:italic>and<jats:italic>n<\/jats:italic>is the size of the input. The second main result is that in case there is an oracle for the redex position, a sequence of<jats:italic>m<\/jats:italic>parallel or single-step rewriting steps under STG-compression can be performed in polynomial time. This generalizes results on DAG-compressed rewriting sequences. Combining these results implies that for an STG-compressed term rewrite system with left-linear rules,<jats:italic>m<\/jats:italic>parallel or single-step term rewrite steps can be performed in polynomial time in the input size<jats:italic>n<\/jats:italic>and<jats:italic>m<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0960129518000208","type":"journal-article","created":{"date-parts":[[2018,8,2]],"date-time":"2018-08-02T01:54:54Z","timestamp":1533174894000},"page":"1415-1450","source":"Crossref","is-referenced-by-count":3,"title":["Linear pattern matching of compressed terms and polynomial rewriting"],"prefix":"10.1017","volume":"28","author":[{"given":"MANFRED","family":"SCHMIDT-SCHAU\u00df","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2018,8,2]]},"reference":[{"key":"S0960129518000208_ref31","unstructured":"Schmidt-Schau\u00df M. (2012). Matching of compressed patterns with character-variables. In: Tiwari A. , (ed.) Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA '12), Leibniz International Proceedings in Informatics, vol. 624, Schloss Dagstuhl 272\u2013287."},{"key":"S0960129518000208_ref23","doi-asserted-by":"crossref","unstructured":"Lohrey M. , Maneth S. and Mennicke R. (2011). Tree structure compression with RePair. In: 2011 Data Compression Conference (DCC 2011), March 29\u201331, 2011, Snowbird, UT, USA, IEEE Computer Society 2011, 353\u2013362.","DOI":"10.1109\/DCC.2011.42"},{"key":"S0960129518000208_ref17","unstructured":"Levy J. , Schmidt-Schau\u00df M. and Villaret M. (2006). Bounded second-order unification is NP-complete. In: Proceedings of the 17th International Conference on Term Rewriting and Applications (RTA), Lecture Notes in Computer Science, vol. 4098, Springer 400\u2013414."},{"key":"S0960129518000208_ref4","doi-asserted-by":"crossref","unstructured":"Busatto G. , Lohrey M. and Maneth S. (2005). Efficient memory representation of XML documents. In: Proceedings of the International Workshop on Database Programming Languages (DBPL 2005), Lecture Notes in Computer Science, vol. 3774, Springer 199\u2013216.","DOI":"10.1007\/11601524_13"},{"key":"S0960129518000208_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.03.003"},{"key":"S0960129518000208_ref16","first-page":"1","article-title":"On constructor rewrite systems and the lambda calculus","volume":"8","author":"Lago","year":"2012","journal-title":"Logical Methods in Computer Science"},{"key":"S0960129518000208_ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1852"},{"key":"S0960129518000208_ref19","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzq010"},{"key":"S0960129518000208_ref1","first-page":"33","volume-title":"Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA '10)","author":"Avanzini","year":"2010"},{"key":"S0960129518000208_ref14","doi-asserted-by":"crossref","unstructured":"Karpinski M. , Rytter W. and Shinohara A. (1995). Pattern-matching for strings with short description. In: Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM '95), Lecture Notes in Computer Science, vol. 937, Springer-Verlag 205\u2013214.","DOI":"10.1007\/3-540-60044-2_44"},{"key":"S0960129518000208_ref15","unstructured":"Lago U.D. and Martini S. (2009). Derivational complexity is an invariant cost model. In: Proceedings of the FOPARA, Lecture Notes in Computer Science, vol. 6324, Springer 100\u2013113."},{"key":"S0960129518000208_ref30","unstructured":"Schmidt-Schau\u00df M. (2005). Polynomial equality testing for terms with shared substructures. Frank report 21, Institut f\u00fcr Informatik. FB Informatik und Mathematik. Goethe-Universit\u00e4t Frankfurt."},{"key":"S0960129518000208_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60207-8_23"},{"key":"S0960129518000208_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752"},{"key":"S0960129518000208_ref13","unstructured":"Jez A. (2012). Faster fully compressed pattern matching by recompression. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), Part I, Lecture Notes in Computer Science, vol. 7391, Springer 533\u2013544."},{"key":"S0960129518000208_ref32","unstructured":"Schmidt-Schau\u00df M. , Sabel D. and Anis A. (2011). Congruence closure of compressed terms in polynomial time. In: Proceedings of the FroCos, Lecture Notes in Computer, vol. 624, Springer 227\u2013242."},{"key":"S0960129518000208_ref34","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"S0960129518000208_ref7","unstructured":"Comon H. , Dauchet M. , Gilleron R. , Jacquemard F. , Lugiez D. , Tison S. and Tommasi M. (1997). Tree automata techniques and applications. release October 2002. Available at http:\/\/tata.gforge.inria.fr\/"},{"key":"S0960129518000208_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970402"},{"key":"S0960129518000208_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294596"},{"key":"S0960129518000208_ref26","doi-asserted-by":"crossref","unstructured":"Plandowski W. (1994). Testing equivalence of morphisms in context-free languages. In: Proceedings of the Annual European Symposium on Algorithms (ESA '94), Lecture Notes in Computer Science, vol. 855, Springer 460\u2013470.","DOI":"10.1007\/BFb0049431"},{"key":"S0960129518000208_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.004"},{"key":"S0960129518000208_ref21","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"S0960129518000208_ref10","doi-asserted-by":"crossref","unstructured":"Gasieniec L. , Karpinski M. , Plandowski W. and Rytter W. (1996a). Efficient algorithms for Lempel\u2013Ziv encoding (extended abstract). In: Karlsson R. G. and Lingas A. (eds.) Proceedings of the SWAT, Lecture Notes in Computer Science, vol. 1097, Springer 392\u2013403.","DOI":"10.1007\/3-540-61422-2_148"},{"key":"S0960129518000208_ref24","unstructured":"Lohrey M. , Maneth S. and Schmidt-Schau\u00df M. (2009). Parameter reduction in grammar-compressed trees. In: Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS), Lecture Notes in Computer Science, vol. 5504, Springer 212\u2013226."},{"key":"S0960129518000208_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.01.008"},{"key":"S0960129518000208_ref28","first-page":"15","volume-title":"Proceedings of the ICALP 2004","author":"Rytter","year":"2004"},{"key":"S0960129518000208_ref11","doi-asserted-by":"crossref","unstructured":"Gasieniec L. , Karpinski M. , Plandowski W. and Rytter W. (1996b). Randomized efficient algorithms for compressed strings: The finger-print approach (extended abstract). In: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM' 96), Lecture Notes in Computer Science, vol. 1075, Springer 39\u201349.","DOI":"10.1007\/3-540-61258-0_3"},{"key":"S0960129518000208_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73437-6_24"},{"key":"S0960129518000208_ref22","unstructured":"Lohrey M. and Maneth S. (2005). The complexity of tree automata and XPath on grammar-compressed trees. In: Proceedings of the 10th International Conference on Implementation and Application of Automata (CIAA'05) 225\u2013237."},{"key":"S0960129518000208_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/050645403"},{"key":"S0960129518000208_ref8","unstructured":"Gasc\u00f3n A. , Godoy G. and Schmidt-Schau\u00df M. (2008). Context matching for compressed terms. In: Proceedings of the 23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008), IEEE Computer Society 93\u2013102."},{"key":"S0960129518000208_ref29","doi-asserted-by":"crossref","unstructured":"Salzer G. (1992). The unification of infinite sets of terms and its applications. In: Proceedings of the LPAR '92, Lecture Notes in Computer Science, vol. 624, 409\u2013420.","DOI":"10.1007\/BFb0013079"},{"key":"S0960129518000208_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00052-7"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129518000208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,21]],"date-time":"2019-10-21T14:39:39Z","timestamp":1571668779000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129518000208\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,2]]},"references-count":34,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S0960129518000208"],"URL":"https:\/\/doi.org\/10.1017\/s0960129518000208","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,2]]}}}