{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:30:56Z","timestamp":1736487056506,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540368342"},{"type":"electronic","value":"9783540368359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11805618_30","type":"book-chapter","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:29:13Z","timestamp":1153837753000},"page":"400-414","source":"Crossref","is-referenced-by-count":9,"title":["Bounded Second-Order Unification Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Jordi","family":"Levy","sequence":"first","affiliation":[]},{"given":"Manfred","family":"Schmidt-Schau\u00df","sequence":"additional","affiliation":[]},{"given":"Mateu","family":"Villaret","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_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":"30_CR2","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (release 1.10.2002) (1997), available on: http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1016\/B978-044450813-3\/50018-7","volume-title":"Handbook of Automated Reasoning, ch. 16","author":"G. Dowek","year":"2001","unstructured":"Dowek, G.: Higher-order unification and matching. In: Robinson, A., Voronkov, A. (eds.) Handbook of Automated Reasoning, ch. 16, vol.\u00a0II, pp. 1009\u20131062. Elsevier Science, Amsterdam (2001)"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0304-3975(06)80003-4","volume":"87","author":"W.M. Farmer","year":"1991","unstructured":"Farmer, W.M.: Simple second-order languages for which unification is undecidable. Theoretical Computer Science\u00a087, 173\u2013214 (1991)","journal-title":"Theoretical Computer Science"},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(81)90040-2","volume":"13","author":"W.D. Goldfarb","year":"1981","unstructured":"Goldfarb, W.D.: The undecidability of the second-order unification problem. Theoretical Computer Science\u00a013, 225\u2013230 (1981)","journal-title":"Theoretical Computer Science"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0304-3975(75)90011-0","volume":"1","author":"G. Huet","year":"1975","unstructured":"Huet, G.: A unification algorithm for typed \u03bb-calculus. Theoretical Computer Science\u00a01, 27\u201357 (1975)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"30_CR7","first-page":"670","volume":"43","author":"A. Ko\u015bcielski","year":"1996","unstructured":"Ko\u015bcielski, A., Pacholski, L.: Complexity of Makanin\u2019s algorithm. J.\u00a0ACM\u00a043(4), 670\u2013684 (1996)","journal-title":"J.\u00a0ACM"},{"key":"30_CR8","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/11532231_11","volume-title":"Automated Deduction \u2013 CADE-20","author":"J. Levy","year":"2005","unstructured":"Levy, J., Niehren, J., Villaret, M.: Well-nested context unification. In: Nieuwenhuis, R. (ed.) CADE 2005. LNCS (LNAI), vol.\u00a03632, pp. 149\u2013163. Springer, Heidelberg (2005)"},{"key":"30_CR9","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":"30_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1006\/inco.2000.2877","volume":"159","author":"J. Levy","year":"2000","unstructured":"Levy, J., Veanes, M.: On the undecidability of second-order unification. Information and Computation\u00a0159, 125\u2013150 (2000)","journal-title":"Information and Computation"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/3-540-45610-4_23","volume-title":"Rewriting Techniques and Applications","author":"J. Levy","year":"2002","unstructured":"Levy, J., Villaret, M.: Currying second-order unification problems. In: Tison, S. (ed.) RTA 2002. LNCS, vol.\u00a02378, pp. 326\u2013339. Springer, Heidelberg (2002)"},{"issue":"2","key":"30_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1070\/SM1977v032n02ABEH002376","volume":"32","author":"G.S. Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Math. USSR Sbornik\u00a032(2), 129\u2013198 (1977)","journal-title":"Math. USSR Sbornik"},{"issue":"2","key":"30_CR13","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 TOPLAS\u00a04(2), 258\u2013282 (1982)","journal-title":"ACM TOPLAS"},{"key":"30_CR14","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":"30_CR15","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"},{"key":"30_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/3-540-44802-0_35","volume-title":"Computer Science Logic","author":"M. Schmidt-Schau\u00df","year":"2001","unstructured":"Schmidt-Schau\u00df, M.: Stratified context unification is in PSPACE. In: Fribourg, L. (ed.) CSL 2001 and EACSL 2001. LNCS, vol.\u00a02142, pp. 498\u2013512. Springer, Heidelberg (2001)"},{"issue":"2","key":"30_CR17","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2003.08.002","volume":"188","author":"M. Schmidt-Schau\u00df","year":"2004","unstructured":"Schmidt-Schau\u00df, M.: Decidability of bounded second order unification. Information and Computation\u00a0188(2), 143\u2013178 (2004)","journal-title":"Information and Computation"},{"key":"30_CR18","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 (November 2005)"},{"key":"30_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BFb0052361","volume-title":"Rewriting Techniques and Applications","author":"M. Schmidt-Schau\u00df","year":"1998","unstructured":"Schmidt-Schau\u00df, M., Schulz, K.U.: On the exponent of periodicity of minimal solutions of context equations. In: Nipkow, T. (ed.) RTA 1998. LNCS, vol.\u00a01379, pp. 61\u201375. Springer, Heidelberg (1998)"},{"key":"30_CR20","doi-asserted-by":"crossref","unstructured":"Schubert, A.: Second-order unification and type inference for church-style polymorphism. In: POPL 1998, pp. 279\u2013288 (1998)","DOI":"10.1145\/268946.268969"}],"container-title":["Lecture Notes in Computer Science","Term Rewriting and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11805618_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T02:16:42Z","timestamp":1736475402000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11805618_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540368342","9783540368359"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11805618_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}