{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:25Z","timestamp":1760202625378,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642243639"},{"type":"electronic","value":"9783642243646"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-24364-6_16","type":"book-chapter","created":{"date-parts":[[2011,9,29]],"date-time":"2011-09-29T01:22:21Z","timestamp":1317259341000},"page":"227-242","source":"Crossref","is-referenced-by-count":2,"title":["Congruence Closure of Compressed Terms in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Manfred","family":"Schmidt-Schauss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Sabel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Altug","family":"Anis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","unstructured":"The Haskell Programming Language (2011), http:\/\/www.haskell.org"},{"issue":"4","key":"16_CR2","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1017\/S0956796800000885","volume":"3","author":"S. Adams","year":"1993","unstructured":"Adams, S.: Efficient sets - a balancing act. J. Funct. Program.\u00a03(4), 553\u2013561 (1993)","journal-title":"J. Funct. Program."},{"key":"16_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752","volume-title":"Term Rewriting and All That","author":"F. Baader","year":"1998","unstructured":"Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, New York (1998)"},{"key":"16_CR4","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)"},{"issue":"4-5","key":"16_CR5","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.is.2008.01.004","volume":"33","author":"G. Busatto","year":"2008","unstructured":"Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML document trees. Inf. Syst.\u00a033(4-5), 456\u2013474 (2008)","journal-title":"Inf. Syst."},{"key":"16_CR6","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 October 2002)"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"P.J. Downey","year":"1980","unstructured":"Downey, P.J., Sethi, R., Tarjan, R.E.: Variations on the common subexpression problem. J. ACM\u00a027, 758\u2013771 (1980)","journal-title":"J. ACM"},{"issue":"1","key":"16_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/138027.138032","volume":"40","author":"J.H. Gallier","year":"1993","unstructured":"Gallier, J.H., Narendran, P., Plaisted, D.A., Raatz, S., Snyder, W.: An algorithm for finding canonical sets of ground rewrite rules in polynomial time. J. ACM\u00a040(1), 1\u201316 (1993)","journal-title":"J. ACM"},{"key":"16_CR9","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco (1979)"},{"key":"16_CR10","first-page":"93","volume-title":"23rd LICS","author":"A. Gasc\u00f3n","year":"2008","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M.: Context matching for compressed terms. In: 23rd LICS, pp. 93\u2013102. IEEE Computer Society, Los Alamitos (2008)"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M.: Unification and matching on compressed terms (2010), http:\/\/arxiv.org\/abs\/1003.1632v1","DOI":"10.1145\/1970398.1970402"},{"key":"16_CR12","unstructured":"Gasc\u00f3n, A., Maneth, S., Ramos, L.: First-Order Unification on Compressed Terms. In: Schmidt-Schau\u00df, M. (ed.) 22nd RTA. LIPIcs, vol.\u00a010, pp. 51\u201360 (2011)"},{"key":"16_CR13","first-page":"164","volume-title":"9th STOC","author":"D. Kozen","year":"1977","unstructured":"Kozen, D.: Complexity of finitely presented algebras. In: 9th STOC, pp. 164\u2013177. ACM, New York (1977)"},{"key":"16_CR14","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":"16_CR15","series-title":"Lecture Notes in Artificial Intelligence","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 (LNAI), vol.\u00a04130, pp. 82\u201396. Springer, Heidelberg (2006)"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Levy, J., Schmidt-Schau\u00df, M., Villaret, M.: On the complexity of bounded second-order unification and stratified context unification (2011) (to appear in Logic J. of the IGPL), http:\/\/www.ki.informatik.uni-frankfurt.de\/papers\/schauss\/","DOI":"10.1093\/jigpal\/jzq010"},{"key":"16_CR17","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)"},{"issue":"5","key":"16_CR18","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 J. Comput.\u00a035(5), 1210\u20131240 (2006)","journal-title":"SIAM J. Comput."},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-642-00596-1_16","volume-title":"Foundations of Software Science and Computational Structures","author":"M. Lohrey","year":"2009","unstructured":"Lohrey, M., Maneth, S., Schmidt-Schau\u00df, M.: Parameter reduction in grammar-compressed trees. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol.\u00a05504, pp. 212\u2013226. Springer, Heidelberg (2009)"},{"issue":"2","key":"16_CR20","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1145\/322186.322198","volume":"27","author":"G. Nelson","year":"1980","unstructured":"Nelson, G., Oppen, D.C.: Fast decision procedures based on congruence closure. J. ACM\u00a027(2), 356\u2013364 (1980)","journal-title":"J. ACM"},{"issue":"6","key":"16_CR21","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1145\/1217856.1217859","volume":"53","author":"R. Nieuwenhuis","year":"2006","unstructured":"Nieuwenhuis, R., Oliveras, A., Tinelli, C.: Solving SAT and SAT Modulo Theories: From an abstract Davis\u2013Putnam\u2013Logemann\u2013Loveland procedure to DPLL(t). J. ACM\u00a053(6), 937\u2013977 (2006)","journal-title":"J. ACM"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms in context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-642-60207-8_23","volume-title":"Jewels are Forever","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Karhum\u00e4ki, J., Maurer, H.A., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 262\u2013272. Springer, Heidelberg (1999)"},{"key":"16_CR24","unstructured":"Schmidt-Schau\u00df, M.: Polynomial equality testing for terms with shared substructures. Frank report\u00a021, Institut f\u00fcr Informatik. FB Informatik und Mathematik. J. W. Goethe-Universit\u00e4t Frankfurt am Main (2005)"},{"key":"16_CR25","unstructured":"Schmidt-Schau\u00df, M.: Pattern matching of compressed terms and contexts and polynomial rewriting. Frank report\u00a043, Institut f\u00fcr Informatik. Goethe-Universit\u00e4t Frankfurt am Main (2011)"},{"issue":"7","key":"16_CR26","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1145\/359545.359570","volume":"21","author":"R.E. Shostak","year":"1978","unstructured":"Shostak, R.E.: An algorithm for reasoning about equality. Commun. ACM\u00a021(7), 583\u2013585 (1978)","journal-title":"Commun. ACM"},{"key":"16_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/3-540-51081-8_123","volume-title":"Rewriting Techniques and Applications","author":"W. Snyder","year":"1989","unstructured":"Snyder, W.: Efficient ground completion: An o(n log n) algorithm for generating reduced sets of ground rewrite rules equivalent to a set of ground equations e. In: Dershowitz, N. (ed.) RTA 1989. LNCS, vol.\u00a0355, pp. 419\u2013433. Springer, Heidelberg (1989)"},{"issue":"4","key":"16_CR28","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1006\/jsco.1993.1029","volume":"15","author":"W. Snyder","year":"1993","unstructured":"Snyder, W.: A fast algorithm for generating reduced ground rewriting systems from a set of ground equations. J. Symb. Comput.\u00a015(4), 415\u2013450 (1993)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"16_CR29","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inform. Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Combining Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24364-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,16]],"date-time":"2019-06-16T14:00:17Z","timestamp":1560693617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24364-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642243639","9783642243646"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24364-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}