{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T07:10:20Z","timestamp":1739171420790,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642023477"},{"type":"electronic","value":"9783642023484"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02348-4_26","type":"book-chapter","created":{"date-parts":[[2009,6,18]],"date-time":"2009-06-18T07:27:21Z","timestamp":1245310041000},"page":"365-379","source":"Crossref","is-referenced-by-count":2,"title":["Unification with Singleton Tree Grammars"],"prefix":"10.1007","author":[{"given":"Adri\u00e0","family":"Gasc\u00f3n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillem","family":"Godoy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred","family":"Schmidt-Schau\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/11601524_13","volume-title":"Database Programming Languages","author":"G. Busatto","year":"2005","unstructured":"Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML documents. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol.\u00a03774, pp. 199\u2013216. Springer, Heidelberg (2005)"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Baader, F., Snyder, W.: Unification theory. In: Robinson, J.A., Voronkov, A. (eds.) Handbook of Automated Reasoning, pp. 445\u2013532. Elsevier\/ MIT Press (2001)","DOI":"10.1016\/B978-044450813-3\/50010-2"},{"key":"26_CR3","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1997), http:\/\/www.grappa.univ-lille3.fr\/tata (release 1.10.2002)"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M.: Context matching for compressed terms. In: 23rd IEEE LICS, pp. 93\u2013102 (2008), http:\/\/www.lsi.upc.edu\/~ggodoy\/publications.html","DOI":"10.1109\/LICS.2008.17"},{"key":"26_CR5","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M., Tiwari, A.: Context Unification with One Context Variable (to be published) (2008)"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/3-540-45995-2_31","volume-title":"LATIN 2002: Theoretical Informatics","author":"B. Genest","year":"2002","unstructured":"Genest, B., Muscholl, A.: Pattern matching and membership for hierarchical message sequence charts. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 326\u2013340. Springer, Heidelberg (2002)"},{"key":"26_CR7","first-page":"132","volume-title":"SPIRE 2000","author":"M. Hirao","year":"2000","unstructured":"Hirao, M., Shinohara, A., Takeda, M., Arikawa, S.: Fully compressed pattern matching algorithm for balanced straight-line programs. In: SPIRE 2000, p. 132. IEEE Computer Society Press, Washington (2000)"},{"key":"26_CR8","first-page":"392","volume-title":"Proc. 4th Scandinavian Workshop on Algorithm Theory","author":"M. Karpinski","year":"1996","unstructured":"Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Proc. 4th Scandinavian Workshop on Algorithm Theory, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-60044-2_44","volume-title":"Combinatorial Pattern Matching","author":"M. Karpinski","year":"1995","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: Pattern-matching for strings with short description. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol.\u00a0937, pp. 205\u2013214. Springer, Heidelberg (1995)"},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-73437-6_24","volume-title":"Combinatorial Pattern Matching","author":"Y. Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: A tractability border. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 228\u2013240. Springer, Heidelberg (2007)"},{"key":"26_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11605157_19","volume-title":"Implementation and Application of Automata","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M., Maneth, S.: The complexity of tree automata and XPath on grammar-compressed trees. In: Farr\u00e9, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol.\u00a03845. Springer, Heidelberg (2006)"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/978-3-642-00596-1_16","volume-title":"FoSSaCS 2009","author":"M. Lohrey","year":"2009","unstructured":"Lohrey, M., Maneth, S., Schmidt-Schau\u00df, M.: Parameter reduction in grammar-compressed trees. In: Alfaro, L. (ed.) FoSSaCS 2009. LNCS, vol.\u00a05504, pp. 212\u2013226. Springer, Heidelberg (2009)"},{"issue":"5","key":"26_CR13","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM Journal on Computing\u00a035(5), 1210\u20131240 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/11821069_56","volume-title":"Mathematical Foundations of Computer Science 2006","author":"S. Lasota","year":"2006","unstructured":"Lasota, S., Rytter, W.: Faster algorithm for bisimulation equivalence of normed context-free processes. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 646\u2013657. Springer, Heidelberg (2006)"},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-540-25979-4_4","volume-title":"Rewriting Techniques and Applications","author":"J. Levy","year":"2004","unstructured":"Levy, J., Schmidt-Schau\u00df, M., Villaret, M.: Monadic second-order unification is NP-complete. In: van Oostrom, V. (ed.) RTA 2004. LNCS, vol.\u00a03091, pp. 55\u201369. Springer, Heidelberg (2004)"},{"key":"26_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/11805618_30","volume-title":"Term Rewriting and Applications","author":"J. Levy","year":"2006","unstructured":"Levy, J., Schmidt-Schau\u00df, M., Villaret, M.: Bounded second-order unification is NP-complete. In: Pfenning, F. (ed.) RTA 2006. LNCS, vol.\u00a04098, pp. 400\u2013414. Springer, Heidelberg (2006)"},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/11814771_8","volume-title":"Automated Reasoning","author":"J. Levy","year":"2006","unstructured":"Levy, J., Schmidt-Schau\u00df, M., Villaret, M.: Stratified context unification is NP-complete. In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS, vol.\u00a04130, pp. 82\u201396. Springer, Heidelberg (2006)"},{"issue":"2","key":"26_CR18","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1145\/357162.357169","volume":"4","author":"A. Martelli","year":"1982","unstructured":"Martelli, A., Montanari, U.: An efficient unification algorithm. ACM Trans. on programming languages and systems\u00a04(2), 258\u2013282 (1982)","journal-title":"ACM Trans. on programming languages and systems"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Maneth, S., Mihaylov, N., Sakr, S.: XML tree structure compression. DEXA, 243\u2013247 (2008)","DOI":"10.1109\/DEXA.2008.41"},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-63220-4_45","volume-title":"Combinatorial Pattern Matching","author":"M. Miyazaki","year":"1997","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. In: Hein, J., Apostolico, A. (eds.) CPM 1997. LNCS, vol.\u00a01264, pp. 1\u201311. Springer, Heidelberg (1997)"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: The Complexity of the Morphism Equivalence Problem for Context-Free Languages. PhD thesis, Department of Mathematics, Informatics and Mechanics, Warsaw University (1995)","DOI":"10.1007\/BFb0049431"},{"issue":"1","key":"26_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"J. Alan Robinson","year":"1965","unstructured":"Alan Robinson, J.: A machine oriented logic based on the resolution principle. J. of the ACM\u00a012(1), 23\u201341 (1965)","journal-title":"J. of the ACM"},{"key":"26_CR23","unstructured":"Schmidt-Schau\u00df, M.: Polynomial equality testing for terms with shared substructures. Frank report\u00a021, FB Informatik und Mathematik. Goethe-Univ. Frankfurt (November 2005)"}],"container-title":["Lecture Notes in Computer Science","Rewriting Techniques and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02348-4_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T06:13:04Z","timestamp":1739167984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02348-4_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642023477","9783642023484"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02348-4_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}