{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T12:06:21Z","timestamp":1749125181453},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631651"},{"type":"electronic","value":"9783540691945"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63165-8_173","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:10:49Z","timestamp":1330297849000},"page":"154-165","source":"Crossref","is-referenced-by-count":10,"title":["Monadic simultaneous rigid E-unification and related problems"],"prefix":"10.1007","author":[{"given":"Yuri","family":"Gurevich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Voronkov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"15_CR1","first-page":"243","volume-title":"Handbook of Theoretical Computer Science, volume B: Formal Methods and Semantics","author":"N. Dershowitz","year":"1990","unstructured":"N. Dershowitz and J.-P. Jouannaud. Rewrite systems. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Methods and Semantics, chapter 6, pages 243\u2013309. North Holland, Amsterdam, 1990."},{"key":"15_CR2","first-page":"???","volume":"60","author":"A. Degtyarev","year":"1996","unstructured":"A. Degtyarev, Yu. Gurevich, and A. Voronkov. Herbrand's theorem and equational reasoning: Problems and solutions. In Bulletin of the European Association for Theoretical Computer Science, volume 60, page---October 1996. The \u201cLogic in Computer Science\u201d column.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"A. Degtyarev, Yu. Gurevich, P. Narendran, M. Veanes, and A. Voronkov. The decidability of simultaneous rigid E-unification with one variable. UPMAIL Technical Report 139, Uppsala University, Computing Science Department, March 1997.","DOI":"10.1007\/BFb0052370"},{"key":"15_CR4","first-page":"494","volume-title":"Simultaneous rigid E-unification and related algorithmic problems","author":"A. Degtyarev","year":"1996","unstructured":"A. Degtyarev, Yu. Matiyasevich, and A. Voronkov. Simultaneous rigid E-unification and related algorithmic problems. In Eleventh Annual IEEE Symposium on Logic in Computer Science (LICS'96), pages 494\u2013502, New Brunswick, NJ, July 1996. IEEE Computer Society Press."},{"issue":"1\u20132","key":"15_CR5","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(96)00092-8","volume":"166","author":"A. Degtyarev","year":"1996","unstructured":"A. Degtyarev and A. Voronkov. The undecidability of simultaneous rigid E-unification. Theoretical Computer Science, 166(1\u20132):291\u2013300, 1996.","journal-title":"Theoretical Computer Science"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Yu. Gurevich and A. Voronkov. Monadic simultaneous rigid E-unification and related problems. UPMAIL Technical Report 137, Uppsala University, Computing Science Department, February 1997.","DOI":"10.1007\/3-540-63165-8_173"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"A. Koscielski and L. Pacholski. Complexity of unification in free groups and free semigroups. In Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, pages 824\u2013829, Los Alamitos, 1990.","DOI":"10.1109\/FSCS.1990.89605"},{"issue":"4","key":"15_CR8","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1145\/234533.234543","volume":"43","author":"A. Koscielski","year":"1996","unstructured":"A. Koscielski and L. Pacholski. Complexity of Makanin's algorithm. Journal of the Association for Computing Machinery, 43(4):670\u2013684, 1996.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"15_CR9","first-page":"164","volume-title":"Complexity of finitely presented algebras","author":"D. Kozen","year":"1977","unstructured":"D. Kozen. Complexity of finitely presented algebras. In Proc. of the 9th Annual Symposium on Theory of Computing, pages 164\u2013177, New York, 1977. ACM."},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"D. Kozen. Lower bounds for natural proof systems. In Proc. 18th IEEE Symposium on Foundations of Computer Science (FOCS), pages 254\u2013266, 1977.","DOI":"10.1109\/SFCS.1977.16"},{"issue":"2","key":"15_CR11","first-page":"147","volume":"103","author":"G.S. Makanin","year":"1977","unstructured":"G.S. Makanin. The problem of solvability of equations in free semigroups. Mat. Sbornik (in Russian), 103(2):147\u2013236, 1977. English Translation in American Mathematical Soc. Translations (2), vol. 117, 1981.","journal-title":"Mat. Sbornik (in Russian)"},{"key":"15_CR12","series-title":"Handbook of Theoretical Computer Science","first-page":"1","volume-title":"Formal Methods and Semantics","author":"D. Perrin","year":"1990","unstructured":"D. Perrin. Finite automata. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Methods and Semantics, chapter 1, pages 1\u201357. Elsevier Science, Amsterdam, 1990."},{"key":"15_CR13","unstructured":"D.A. Plaisted. Special cases and substitutes for rigid E-unification. Technical Report MPI-I-95-2-010, Max-Planck-Institut f\u00fcr Informatik, November 1995."},{"key":"15_CR14","unstructured":"K.U. Schulz. Makanin's algorithm: Two improvements and a generalization. In K.U. Schulz, editor, Word Equations and Related Topics, volume 572 of Lecture Notes in Computer Science, T\u00fcbingen, Germany, October 1990."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1145\/359545.359570","volume":"21","author":"R. Shostak","year":"1978","unstructured":"R. Shostak. An algorithm for reasoning about equality. Communications of the ACM, 21:583\u2013585, July 1978.","journal-title":"Communications of the ACM"},{"key":"15_CR16","unstructured":"M. Veanes. Uniform representation of recursively enumerable sets with simultaneous rigid E-unification. UPMAIL Technical Report 126, Uppsala University, Computing Science Department, 1996."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63165-8_173.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:16:22Z","timestamp":1605647782000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63165-8_173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631651","9783540691945"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-63165-8_173","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}