{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:26Z","timestamp":1725664526742},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540593409"},{"type":"electronic","value":"9783540492375"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59340-3_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:15:00Z","timestamp":1330276500000},"page":"39-53","source":"Crossref","is-referenced-by-count":4,"title":["Word problem for Thue systems with a few relations"],"prefix":"10.1007","author":[{"given":"Yuri","family":"Matiyasevich","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"4_CR1","first-page":"23","volume":"133","author":"S. I. Adian","year":"1973","unstructured":"S. I. Adian. On P. S. Novikov's and his disciple's investigations on algorithmical problems in algebra (in Russian). Trudy Mat. Inst. Steklov., 133:23\u201332, 1973.","journal-title":"Trudy Mat. Inst. Steklov."},{"key":"4_CR2","first-page":"197","volume":"168","author":"S. I. Adian","year":"1984","unstructured":"S. I. Adian and G. S. Makanin. Investigations on algorithmical problems in algebra (in Russian). Trudy Mat. Inst. Steklov., 168:197\u2013217, 1984.","journal-title":"Trudy Mat. Inst. Steklov."},{"issue":"2","key":"4_CR3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.2307\/1970103","volume":"70","author":"W. W. Boone","year":"1959","unstructured":"W. W. Boone. The word problem. Ann. Math., 70(2):207\u2013265, 1959.","journal-title":"Ann. Math."},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0049-237X(08)70841-3","volume-title":"Proceedings of the Second Scandinavian Logic Symposium, volume 63 of Studies in Logic and the Foundations of Mathematics","author":"W. W. Boone","year":"1971","unstructured":"W. W. Boone, D. Collins, and Ju. V. Matijasevi\u010d. Embedding into semigroups with only a few defining relations. In J. E. Fenstad, editor, Proceedings of the Second Scandinavian Logic Symposium, volume 63 of Studies in Logic and the Foundations of Mathematics, pages 27\u201340, Amsterdam, 1971. North-Holland."},{"issue":"1","key":"4_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S1446788700019066","volume":"18","author":"W. W. Boone","year":"1974","unstructured":"W. W. Boone and D. J. Collins. Embeddings into groups with only a few defining relations. J. Austral. Math. Soc., 18(1):1\u20137, 1974.","journal-title":"J. Austral. Math. Soc."},{"issue":"5","key":"4_CR6","first-page":"521","volume":"6","author":"V. V. Borisov","year":"1969","unstructured":"V. V. Borisov. Simple examples of groups with undecidable word problem (in Russian). Mat. Zametki, 6(5):521\u2013532, 1969.","journal-title":"Mat. Zametki"},{"issue":"1","key":"4_CR7","doi-asserted-by":"crossref","first-page":"16","DOI":"10.2307\/1970200","volume":"77","author":"J. L. Britton","year":"1963","unstructured":"J. L. Britton. The word problem. Ann. Math., 77(1):16\u201332, 1963.","journal-title":"Ann. Math."},{"key":"4_CR8","volume-title":"Fernstndeinkurs f\u00fcr die Fernuniversit\u00e4t Hagen","author":"V. Claus","year":"1979","unstructured":"V. Claus. Die Grenze zwischen Entscheidbarkeit und Nichtentscheidbarkeit. Fernstndeinkurs f\u00fcr die Fernuniversit\u00e4t Hagen, Open University, Hagen, 1979."},{"key":"4_CR9","first-page":"54","volume":"12","author":"V. Claus","year":"1980","unstructured":"V. Claus. Some remarks on PCP(k) and related problems. Bull. EATCS, 12:54\u201361, 1980.","journal-title":"Bull. EATCS"},{"issue":"2","key":"4_CR10","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1215\/ijm\/1256044631","volume":"30","author":"D. J. Collins","year":"1986","unstructured":"D. J. Collins. A simple presentation of a group with unsolvable word problem. Illinois J. Math., 30(2):230\u2013234, 1986.","journal-title":"Illinois J. Math."},{"issue":"4","key":"4_CR11","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1002\/malq.19690152001","volume":"15","author":"D. J. Collins","year":"1969","unstructured":"D. J. Collins. Word and conjugacy problems in groups with only a few defining relations. Z. Math. Logik Grundlag. Math., 15(4):305\u2013323, 1969.","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"4_CR12","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01455155","volume":"69","author":"M. Dehn","year":"1910","unstructured":"M. Dehn. \u00dcber die Topologie des dreidimensionalen Raumes. Math. Ann., 69:137\u2013168, 1910.","journal-title":"Math. Ann."},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01456932","volume":"71","author":"M. Dehn","year":"1912","unstructured":"M. Dehn. \u00dcber unendliche diskontinuierliche Gruppen. Math. Ann., 71:116\u2013144, 1912.","journal-title":"Math. Ann."},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1007\/3-540-10843-2_33","volume":"115","author":"A. Ehrenfeucht","year":"1981","unstructured":"A. Ehrenfeucht and G. Rozenberg. On the (generalized) Post correspondence problem with lists of length 2. Lect. Notes Comput. Sci., 115:408\u2013416, 1981.","journal-title":"Lect. Notes Comput. Sci."},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"115","DOI":"10.2307\/2266511","volume":"14","author":"M. J. Hall","year":"1949","unstructured":"M. J. Hall. The word problem for semigroups with two generators. J. Symbolic Logic, 14:115\u2013118, 1949.","journal-title":"J. Symbolic Logic"},{"issue":"1311","key":"4_CR16","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1098\/rspa.1961.0132","volume":"262","author":"G. Higman","year":"1961","unstructured":"G. Higman. Subgroups of finitely presented groups. Proc. Roy. Soc., 262(1311):455\u2013475, 1961.","journal-title":"Proc. Roy. Soc."},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/BFb0087129","volume":"586","author":"G. Lallement","year":"1977","unstructured":"G. Lallement. Presentations de monoides et problems algorithmiques. Lecture Notes in Mathematics, 586:136\u2013144, 1977.","journal-title":"Lecture Notes in Mathematics"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"G. Lallement. The word problem for Thue rewriting systems. This volume, 1994.","DOI":"10.1007\/3-540-59340-3_3"},{"issue":"3","key":"4_CR19","first-page":"457","volume":"42","author":"J. Lockhart","year":"1977","unstructured":"J. Lockhart. Triviality problem for semigroups of deficiency 1. J. Symbolic Logic, 42(3):457\u2013458, 1977.","journal-title":"J. Symbolic Logic"},{"key":"4_CR20","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01455888","volume":"106","author":"W. Magnus","year":"1932","unstructured":"W. Magnus. Das Identit\u00e4ts problem f\u00fcr Gruppen mit einer definierenden Relation. Math. Ann., 106:295\u2013307, 1932.","journal-title":"Math. Ann."},{"key":"4_CR21","first-page":"1478","volume":"7","author":"G. S. Makanin","year":"1966","unstructured":"G. S. Makanin. On the word problem for finitely presented semigroups. Soviet Math. Doklady, 7:1478\u20131480, 1966.","journal-title":"Soviet Math. Doklady"},{"key":"4_CR22","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/3-540-53904-2_114","volume":"488","author":"C. March\u00e9","year":"1991","unstructured":"C. March\u00e9. On ground AC-completion. Lect. Notes Comput. Sci., 488:411\u2013422, 1991.","journal-title":"Lect. Notes Comput. Sci."},{"issue":"7","key":"4_CR23","first-page":"587","volume":"55","author":"A. A. Markoff","year":"1947","unstructured":"A. A. Markoff. Impossibility of certain algorithms in the theory of associative systems (in Russian). Dokl. Akad. Nauk SSSR, 55(7):587\u2013590, 1947.","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"3","key":"4_CR24","first-page":"353","volume":"58","author":"A. A. Markoff","year":"1947","unstructured":"A. A. Markoff. Impossibility of certain algorothms in the theory of associative systems (in Russian). Dokl. Akad. Nauk SSSR, 58(3):353\u2013356, 1947.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4_CR25","unstructured":"A. A. Markoff. Theory of algorithms (in Russian). Trudy Mat. Inst. Steklov., 42, 1954. Translated in Israel Program of scientific Translations. Jerusalem, 1961. MR 17, 1038, MR 24, A2527."},{"key":"4_CR26","first-page":"1264","volume":"173","author":"Y. Matiyasevich","year":"1967","unstructured":"Yu. Matiyasevich. Simple examples of undecidable associative calculi (in Russian). Dokl. Akad. Nauk SSSR, 173:1264\u20131266, 1967. English translation in: Soviet Math. Dokl., 8:555\u2013557, 1967.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4_CR27","first-page":"50","volume":"93","author":"Y. Matiyasevich","year":"1967","unstructured":"Yu. Matiyasevich. Simple examples of undecidable canonical calculi (in Russian). Trudy Mat. Inst. Steklov., 93:50\u201388, 1967. English translation in: Proc Steklov Inst. Math., 93:227\u2013252, 1968.","journal-title":"Trudy Mat. Inst. Steklov."},{"issue":"3","key":"4_CR28","first-page":"520","volume":"196","author":"V. L. Murskii","year":"1971","unstructured":"V. L. Murskii. Unrecognizable properties of finite systems of identity relations (in Russian). Dokl. Akad. Nauk SSSR, 196(3):520\u2013522, 1971.","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"4","key":"4_CR29","first-page":"709","volume":"85","author":"P. S. Novikov","year":"1952","unstructured":"P. S. Novikov. On algorithmical undecidability of the word problem in the theory of groups (in Russian). Dokl. Akad. Nauk SSSR, 85(4):709\u2013712, 1952.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4_CR30","unstructured":"P. S. Novikov. On algorithmical undecidability of the word problem in the theory of groups (in Russian). Trudy Mat. Inst. Steklov., 44, 1955."},{"issue":"5","key":"4_CR31","first-page":"233","volume":"12","author":"J. J. Pansiot","year":"1981","unstructured":"J. J. Pansiot. A note on Post's correspondence problem. 12(5):233, 1981.","journal-title":"A note on Post's correspondence problem"},{"key":"4_CR32","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","volume":"52","author":"E. L. Post","year":"1946","unstructured":"E. L. Post. A variant of recursively unsolvable problem. Bull. Amer. Math. Soc., 52:264\u2013268, 1946.","journal-title":"Bull. Amer. Math. Soc."},{"key":"4_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"E. L. Post","year":"1947","unstructured":"E. L. Post. Recursive unsolvability of a problem of Thue. J. Symbolic Logic, 12:1\u201311, 1947.","journal-title":"J. Symbolic Logic"},{"issue":"2","key":"4_CR34","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1002\/malq.19790250710","volume":"25","author":"L. Priese","year":"1979","unstructured":"L. Priese. \u00dcber ein 2-dimensionales Thue-System mit zwei Regeln und unentscheid-baren Wortproblem. Z. Math. Logik Grundlag. Math., 25(2):179\u2013192, 1979.","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"4_CR35","first-page":"111","volume":"21","author":"D. Scott","year":"1956","unstructured":"D. Scott. A short recursively unsolvable problem. J. Symbolic Logic, 21:111\u2013112, 1956.","journal-title":"J. Symbolic Logic"},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues. Some undecidable termination problem for semi-Thue systems. To appear in Lect. Notes Comput. Sci., 1994","DOI":"10.1007\/3-540-56868-9_32"},{"key":"4_CR37","unstructured":"A. Thue. Probleme \u00fcber Ver\u00e4nderungen von Zeichenreihen nach gegebenen Regeln. Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-naturvidenskabelig klasse, 10, 34pp., 1914. Reprinted in: A. Thue. Selected Mathematical Papers. Oslo, 1977, 493\u2013524."},{"issue":"3","key":"4_CR38","first-page":"370","volume":"107","author":"G. S. Tseitin","year":"1956","unstructured":"G. S. Tseitin. An associative calculus with undecidable problem of equivalence (in Russian). Dokl. Akad. Nauk SSSR, 107(3):370\u2013371, 1956.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4_CR39","first-page":"172","volume":"52","author":"G. S. Tseitin","year":"1958","unstructured":"G. S. Tseitin. An associative calculus with undecidable problem of equivalence (in Russian). Trudy Mat. Inst. Steklov., 52:172\u2013189, 1958.","journal-title":"Trudy Mat. Inst. Steklov."},{"key":"4_CR40","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0012-365X(77)90153-4","volume":"17","author":"M. K. Valiev","year":"1977","unstructured":"M. K. Valiev. Universal group with twenty-one defining relation. Discrete Math., 17:207\u2013213, 1977.","journal-title":"Discrete Math."},{"issue":"2","key":"4_CR41","first-page":"265","volume":"211","author":"M. K. Valiev","year":"1973","unstructured":"M. K. Valiev. Examples of universal finitely-presented groups (in Russian). Dokl. Akad. Nauk SSSR, 211(2):265\u2013268, 1973.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"M. K. Valiev. On polynomial reducibility of word problem under embedding of recursively presented groups in finitely presented groups. In J. Be\u010dv\u00e1\u0159, editor, Mathematical Foundations of Computer Science 1975, volume 32 of Lect. Notes Comput. Sci., pages 432\u2013438. Springer-Verlag, 1975.","DOI":"10.1007\/3-540-07389-2_229"},{"issue":"4","key":"4_CR43","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1090\/S0002-9939-1970-0268257-9","volume":"26","author":"A. Yasuhara","year":"1970","unstructured":"A. Yasuhara. The solvability of the word problem for certain semigroups. Proc. Amer. Math. Soc., 26(4):645\u2013650, 1970.","journal-title":"Proc. Amer. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Term Rewriting"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59340-3_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:26:58Z","timestamp":1605648418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59340-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540593409","9783540492375"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/3-540-59340-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}