{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:48:09Z","timestamp":1725468489566},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055810","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T13:36:31Z","timestamp":1155821791000},"page":"597-606","source":"Crossref","is-referenced-by-count":5,"title":["\u2200\u2203*-Equational theory of context unification is \u03c010-hard"],"prefix":"10.1007","author":[{"given":"Sergei","family":"Vorobyov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"57_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02017493","volume":"26","author":"J. R. B\u00fcchi","year":"1986","unstructured":"J. R. B\u00fcchi and S. Senger. Coding in the existential theory of concatenation. Archive of Mathematical Logic, 26:101\u2013106, 1986.","journal-title":"Archive of Mathematical Logic"},{"key":"57_CR2","doi-asserted-by":"crossref","unstructured":"V. Durnev. Studying algorithmic problems for free semi-groups and groups. In Logical; Foundations of Computer Science (LFCS'97), volume 1234 of Lect. Notes Comput. Sci., pages 88\u2013101. Springer-Verlag, 1997.","DOI":"10.1007\/3-540-63045-7_10"},{"issue":"4","key":"57_CR3","first-page":"772","volume":"211","author":"V. G. Durnev","year":"1973","unstructured":"V. G. Durnev. Positive theory of a free semigroup. Soviet Math. Doklady, 211(4):772\u2013774, 1973.","journal-title":"Soviet Math. Doklady"},{"key":"57_CR4","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0168-0072(88)90015-2","volume":"39","author":"W. Farmer","year":"1988","unstructured":"W. Farmer. A unification algorithm for second-order monadic terms. Annals Pure Appl. Logic, 39:131\u2013174, 1988.","journal-title":"Annals Pure Appl. Logic"},{"key":"57_CR5","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0304-3975(06)80003-4","volume":"87","author":"W. Farmer","year":"1991","unstructured":"W. Farmer. Simple second-order languages for which unification is undecidable. Theor. Comput. Sci., 87:25\u201341, 1991.","journal-title":"Theor. Comput. Sci."},{"key":"57_CR6","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(81)90040-2","volume":"13","author":"W. D. Goldfarb","year":"1981","unstructured":"W. D. Goldfarb. The undecidability of the second-order unification problem. Theor. Comput. Sci., 13:225\u2013230, 1981.","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"57_CR7","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1070\/SM1977v032n02ABEH002376","volume":"32","author":"G. S. Makanin","year":"1977","unstructured":"G. S. Makanin. The problem of solvability of equations in a free semigroup. Math USSR Sbornik, 32(2):127\u2013198, 1977.","journal-title":"Math USSR Sbornik"},{"issue":"1","key":"57_CR8","first-page":"196","volume":"23","author":"S. S. Marchenkov","year":"1982","unstructured":"S. S. Marchenkov. Undecidability of the positive \u2200\u2203-theory of a free semigroup. Siberian Math. Journal, 23(1):196\u2013198, 1982.","journal-title":"Siberian Math. Journal"},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"J. Niehren, M. Pinkal, and P. Ruhrberg. On equality up-to constraints over finite trees, context unification, and one-step rewriting. In W. McCune, editor, CADE-14, volume 1249 of Lect. Notes Comput. Sci., pages 34\u201348. Springer-Verlag, 1997.","DOI":"10.1007\/3-540-63104-6_4"},{"issue":"4","key":"57_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.2307\/2268308","volume":"11","author":"W. V. Quine","year":"1946","unstructured":"W. V. Quine. Concatenation as a basis for arithmetic. J. Symb. Logic, 11(4):105\u2013114, 1946.","journal-title":"J. Symb. Logic"},{"key":"57_CR11","unstructured":"M. Schmidt-Schau\u00df. Unification of stratified second-order terms. Interner Bericht 12\/94, University of Frankfurt am Main, 1994."},{"key":"57_CR12","doi-asserted-by":"crossref","unstructured":"M. Schmidt-Schau\u00df and K. U. Schulz. On the exponent of periodicity of minimal solutions of context equations. In Rewriting Techniques and Applications'98, volume 1379 of Lect. Notes Comput. Sci., pages 61\u201375. Springer-Verlag, 1998.","DOI":"10.1007\/BFb0052361"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055810","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T14:44:23Z","timestamp":1555771463000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0055810","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}