{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:09Z","timestamp":1725664989027},"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_218","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:12:20Z","timestamp":1330297940000},"page":"638-648","source":"Crossref","is-referenced-by-count":4,"title":["The word matching problem is undecidable for finite special string-rewriting systems that are confluent"],"prefix":"10.1007","author":[{"given":"Paliath","family":"Narendran","sequence":"first","affiliation":[]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"F. Baader and J.S. Siekmann. Unification theory. In: D.M. Gabbay, C.J. Hogger, and J.A. Robinson (eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Oxford University Press, 1994.","DOI":"10.1093\/oso\/9780198537465.003.0002"},{"key":"60_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9771-7","volume-title":"String-Rewriting Systems","author":"R. Book","year":"1993","unstructured":"R. Book and F. Otto. String-Rewriting Systems. Springer Verlag, New York, 1993."},{"key":"60_CR3","first-page":"51","volume":"20","author":"Y. Cochet","year":"1976","unstructured":"Y. Cochet. Church-Rosser congruences on free semigroups. Colloquia Mathematica Societatis J\u00e1nos Bolyai 20 (1976) 51\u201360.","journal-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai"},{"key":"60_CR4","first-page":"243","volume-title":"Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics","author":"N. Dershowitz","year":"1990","unstructured":"N. Dershowitz and J.P. Jouannaud. Rewrite systems. In: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, Elsevier, Amsterdam, 1990, pages 243\u2013320."},{"key":"60_CR5","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/78935.78938","volume":"37","author":"J. Jaffar","year":"1990","unstructured":"J. Jaffar. Minimal and complete word unification. Journal Association Computing Machinery 37 (1990) 47\u201385.","journal-title":"Journal Association Computing Machinery"},{"key":"60_CR6","unstructured":"J.P. Jouannaud and C. Kirchner. Solving equations in abstract algebras: a rule-based survey of unification. In: J.L. Lassez and G. Plotkin (eds.), Computational Logic: Essays in Honor of Alan Robinson, MIT Press, 1991, pages 360\u2013394."},{"key":"60_CR7","unstructured":"A. Ko\u015bcielski and L. Pacholski. Makanin's group algorithm is not primitive recursive. Theoretical Computer Science, to appear."},{"key":"60_CR8","first-page":"147","volume":"103","author":"G.S. Makanin","year":"1977","unstructured":"G.S. Makanin. The problem of solvability of equations in a free semigroup. Mat. Sbornik 103 (1977) 147\u2013236.","journal-title":"Mat. Sbornik"},{"key":"60_CR9","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1070\/IM1983v021n03ABEH001803","volume":"21","author":"G.S. Makanin","year":"1983","unstructured":"G.S. Makanin. Equations in a free group. Math. USSR Izvestija 21 (1983) 483\u2013546.","journal-title":"Math. USSR Izvestija"},{"key":"60_CR10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1070\/IM1985v025n01ABEH001269","volume":"25","author":"G.S. Makanin","year":"1985","unstructured":"G.S. Makanin. Decidability of the universal and positive theories of a free group. Math. USSR Izvestija 25 (1985) 75\u201388.","journal-title":"Math. USSR Izvestija"},{"key":"60_CR11","series-title":"Lecture Notes Computer Science 812","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/3-540-58131-6_51","volume-title":"Results and Trends in Theoretical Computer Science","author":"G.S. Makanin","year":"1994","unstructured":"G.S. Makanin and H. Abdulrab. On general solution of word equations. In: J. Karhum\u00e4ki, H. Maurer, and G. Rozenberg (eds.), Results and Trends in Theoretical Computer Science, Lecture Notes Computer Science 812, Springer Verlag, Berlin, 1994, pages 251\u2013263."},{"key":"60_CR12","series-title":"Lecture Notes in Artificial Intelligence 449","first-page":"276","volume-title":"Proceedings 10th CADE","author":"P. Narendran","year":"1990","unstructured":"P. Narendran and F. Otto. Some results on equational unification. In: M.E. Stickel (ed.), Proceedings 10th CADE, Lecture Notes in Artificial Intelligence 449, Springer Verlag, Berlin, 1990, pages 276\u2013291."},{"key":"60_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(94)00208-G","volume":"53","author":"F. Otto","year":"1995","unstructured":"F. Otto. Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general. Information Processing Letters 53 (1995) 237\u2013242.","journal-title":"Information Processing Letters"},{"key":"60_CR14","volume-title":"These 3e Cycle","author":"J.P. Pecuchet","year":"1981","unstructured":"J.P. Pecuchet. Equations avec Constantes et Algorithme de Makanin. These 3e Cycle, Universit\u00e9 de Rouen, France, Dec. 1981."},{"key":"60_CR15","series-title":"Lecture Notes Computer Science 572","first-page":"85","volume-title":"Makanin's algorithm for word equations-Two improvements and a generalization","author":"K.U. Schulz","year":"1990","unstructured":"K.U. Schulz. Makanin's algorithm for word equations-Two improvements and a generalization. In: K.U. Schulz (ed.), Word Equations and Related Topics, Proceedings, Lecture Notes Computer Science 572, Springer Verlag, Berlin, 1990, pages 85\u2013150."},{"key":"60_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF00881904","volume":"11","author":"K.U. Schulz","year":"1993","unstructured":"K.U. Schulz. Word unification and transformation of generalized equations. Journal of Automated Reasoning 11 (1993) 149\u2013184.","journal-title":"Journal of Automated Reasoning"}],"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_218.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T18:07:42Z","timestamp":1713636462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63165-8_218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631651","9783540691945"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-63165-8_218","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}