{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:31:14Z","timestamp":1740547874220,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540221531"},{"type":"electronic","value":"9783540259794"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-25979-4_4","type":"book-chapter","created":{"date-parts":[[2010,9,11]],"date-time":"2010-09-11T01:32:53Z","timestamp":1284168773000},"page":"55-69","source":"Crossref","is-referenced-by-count":6,"title":["Monadic Second-Order Unification Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Jordi","family":"Levy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred","family":"Schmidt-Schau\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mateu","family":"Villaret","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0168-0072(88)90015-2","volume":"39","author":"W.M. Farmer","year":"1988","unstructured":"Farmer, W.M.: A unification algorithm for second-order monadic terms. Annals of Pure and Applied Logic\u00a039, 131\u2013174 (1988)","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR2","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 wich unification is undecidable. Theoretical Computer Science\u00a087, 173\u2013214 (1991)","journal-title":"Theoretical Computer Science"},{"key":"4_CR3","volume-title":"\u201cComputers and Intractability\u201d: A guide to the theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: \u201cComputers and Intractability\u201d: A guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco (1979)"},{"key":"4_CR4","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":"4_CR5","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":"4_CR6","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1145\/234533.234543","volume":"43","author":"A. Ko\u015bcielski","year":"1996","unstructured":"Ko\u015bcielski, A., Pacholski, L.: Complexity of Makanin\u2019s algorithm. Journal of the ACM\u00a043(4), 670\u2013684 (1996)","journal-title":"Journal of the ACM"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BFb0052360","volume-title":"Rewriting Techniques and Applications","author":"J. Levy","year":"1998","unstructured":"Levy, J.: Decidable and undecidable second-order unification problems. In: Nipkow, T. (ed.) RTA 1998. LNCS, vol.\u00a01379, pp. 47\u201360. Springer, Heidelberg (1998)"},{"key":"4_CR8","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":"4_CR9","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":"4_CR10","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"},{"key":"4_CR11","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":"4_CR12","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":"4_CR13","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. In: Proc. of the 40th IEEE Annual Symposium on Foundations of Computer Science (FOCS 1999), pp. 495\u2013500 (1999)","DOI":"10.1109\/SFFCS.1999.814622"},{"key":"4_CR14","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":"4_CR15","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":"4_CR16","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)"},{"issue":"5","key":"4_CR17","first-page":"120","volume":"5","author":"A.P. Zhezherun","year":"1979","unstructured":"Zhezherun, A.P.: Decidability of the unification problem for second order languages with unary function symbols. Kibernetika (Kiev)\u00a05, 120\u2013125 (1979); Translated as Cybernetics\u00a015(5), 735\u2013741 (1980)","journal-title":"Kibernetika (Kiev)"}],"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-540-25979-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T18:08:01Z","timestamp":1740506881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-25979-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540221531","9783540259794"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-25979-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}