×

Decision problems for semi-Thue systems with a few rules. (English) Zbl 1078.03033

Summary: We show that the accessibility problem, the common descendant problem, the termination problem and the uniform termination problem are undecidable for 3-rules semi-Thue systems. As a corollary we obtain the undecidability of the Post correspondence problem for 7 rules.

MSC:

03D03 Thue and Post systems, etc.
68Q42 Grammars and rewriting systems
03D35 Undecidability and degrees of sets of sentences
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] S.I. Adjan, G.S. Makanin, Investigations on algorithmic problems in algebra (in Russian), Trudy Mat. Inst. Steklov. 168 (1984) 197-217, English translation in Proceedings of the Steklov Institute of Mathematics, Vol. 168, 1986, pp. 207-226.
[2] Blondel, V.D.; Canterini, V., Undecidable problems for probabilistic automata of fixed dimension, Theory comput. syst., 36, 3, 231-245, (2003) · Zbl 1039.68061
[3] Book, R.; Otto, F., String rewriting systems, texts and monographs in computer science, (1993), Springer Berlin
[4] Cassaigne, J.; Harju, T.; Karhumäki, J., On the undecidability of freeness of matrix semigroups, Internat. J. algebra comput., 9, 3-4, 295-305, (1999) · Zbl 1029.20027
[5] Cassaigne, J.; Karhumäki, J., Examples of undecidable problems for 2-generator matrix semi-groups, Theoret. comput. sci., 204, 29-34, (1998) · Zbl 0913.68068
[6] Claus, V., Some remarks on PCP(k) and related problems, Bull. EATCS, 12, 54-61, (1980)
[7] Collins, D.J., Word and conjugacy problems in groups with only a few defining relations, Z. math. logik grundlag. math., 15, 4, 305-323, (1969) · Zbl 0188.02903
[8] Dauchet, M., Simulation of Turing machines by a left-linear rewrite rule, (), 109-120
[9] Davis, M., Computability and unsolvability, (1958), McGraw-Hill New York, reprinted by Dover Publications, New York, 1982 · Zbl 0080.00902
[10] Dershowitz, N., Termination of rewriting, J. symbolic comput., 3, 69-116, (1987) · Zbl 0637.68035
[11] Dershowitz, N.; Jouannaud, J.P., Rewrite systems, (), 243-320, (Chapter 2) · Zbl 0900.68283
[12] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., The (generalized) post correspondence problem with lists consisting of two words is decidable, Theoret. comput. sci., 21, 2, 119-144, (1982) · Zbl 0493.68076
[13] Geser, A., Decidability of termination of grid string rewriting rules, SIAM J. comput., 31, 4, 1156-1168, (2002), (electronic) · Zbl 1008.68063
[14] Geser, A.; Middeldorp, A.; Ohlebusch, E.; Zantema, H., Relative undecidability in term rewriting. I. the termination hierarchy, Inform. and comput., 178, 1, 101-131, (2002) · Zbl 1012.68096
[15] Geser, A.; Zantema, H., Non-looping string rewriting, Theor. inform. appl., 33, 3, 279-301, (1999) · Zbl 0951.68054
[16] Halava, V.; Harju, T.; Hirvensalo, M., Generalized post correspondence problem for marked morphisms, Internat. J. algebra comput., 10, 6, 757-772, (2000) · Zbl 0971.68124
[17] Hooper, P., The undecidability of the Turing machine immortality problem, J. symbolic logic, 31, 2, 219-234, (1966) · Zbl 0173.01201
[18] Huet, G., Confluent reductionsabstract properties and applications to term rewriting systems, J. assoc. comput. Mach., 27, 4, 797-821, (1980) · Zbl 0458.68007
[19] M. Jantzen, Confluent String Rewriting, EATCS Monograph, Vol. 14, Springer, Berlin, 1988. · Zbl 1097.68572
[20] Kobayashi, Y.; Katsura, M.; Shikishima-Tsuji, K., Termination and derivational complexity of confluent one-rule string-rewriting systems, Theoret. comput. sci., 262, 1-2, 583-632, (2001) · Zbl 0992.68120
[21] Kurth, W., One-rule semi-thue systems with loops of length one two or three, RAIRO inform. theor. appl., 30, 5, 415-429, (1996) · Zbl 0867.68064
[22] Lallement, G., The word problem for thue rewriting systems, (), 27-38
[23] Markov, A.A., Impossibility of certain algorithms in the theory of associative systems, Dokl. akad. nauk. SSSR, 55, 7, 587-590, (1947), (in Russian), reprinted in his Selected Papers, Vol. 2, MTsNMO Publisher, Moscow, 2003, pp. 3-7 (in Russian)
[24] Markov, A.A., Impossibility of certain algorithms in the theory of associative systems, Dokl. akad. nauk. SSSR, 58, 353-356, (1947), (in Russian), reprinted in his Selected Papers, Vol. 2, MTsNMO Publisher, Moscow, 2003, pp. 13-17 (in Russian) · Zbl 0030.19401
[25] Yu.V. Matiyasevich, Simple examples of undecidable associative calculi, Dokl. AN SSSR 173 (16) (in Russian), English translation in Soviet Math. Dokl. 8 (1967) 555-557. · Zbl 0189.01102
[26] Matiyasevich, Yu.V., Simple examples of unsolvable canonical calculi, Trudy mat. inst. Steklov, 93, 50-88, (1967), (in Russian), English translation in Proc. Steklov Inst. Math. 93 (1967) 61-110
[27] Matiyasevich, Yu.V., On investigations on some algorithmic problems in algebra and number theory, trudy matematicheskogo instituta im. V. A. steklova, 168, 218-235, (1984), (in Russian), English translation in Proc. Steklov Inst. Math. 168(3) (1986) 227-252 · Zbl 0597.03020
[28] Matiyasevich, Yu., Word problem for thue systems with a few relations, in: term rewriting (font romeux, 1993), (), 39-53
[29] Matiyasevich, Yu.; Sénizergues, G., Decision problems for semi-thue systems with a few rules, (), 523-531
[30] McNaughton, R., Semi-thue systems with an inhibitor, J. automat. reason., 26, 4, 409-431, (2001) · Zbl 0981.68073
[31] Post, E.L., Formal reductions of the general combinatorial decision problem, Amer. J. math., 65, 197-215, (1943) · Zbl 0063.06327
[32] Post, E.L., Recursive unsolvability of a problem of thue, J. symbolic logic, 12, 1, 1-11, (1947), reprinted in: M. Davis (Ed.), Solvability, Provability, Definability: The Collected Works of Emil L. Post, Birkhäuser, Boston a.o., 1994, pp. 503-513 · Zbl 1263.03030
[33] Sénizergues, G., Some undecidable termination problems for semi-thue systems, Theoret. comput. sci., 142, 257-276, (1995) · Zbl 0873.68054
[34] G. Sénizergues, On the termination-problem for one-rule semi-Thue systems, in: RTA 96, Lecture Notes in Computer Science 1103 (1996) 302-316.
[35] Steinby, M.; Thomas, W., Trees and term rewriting in 1910on a paper by axel thue, Bull. eur. assoc. theoret. comput. sci. EATCS (, 72), 256-269, (2000)
[36] A. Thue. Probleme über veränderungen von zeichenreihen nach gegebenen regeln, Skr. Vid. Kristiania, I Mat. Naturv. Klasse 10 (1914) 34. Reprinted in his Selected Mathematical Papers, Universitetsforlaget, Oslo, 1977, pp. 493-524.
[37] A. Thue, Die lösung eines spezialfalles eines generellen logichen problems, Kra. Videnskabs-Selskabets Skrifter. I. Mat. Nat. Kl.nr 8. Reprinted in his Selected Mathematical Papers, Universitetsforlaget, Oslo, 1977, pp. 273-310.
[38] Zantema, H.; Geser, A., A complete characterization of termination of \(0^p 1^q \rightarrow 1^r 0^s\), Appl. algebra eng. comm. comput., 11, 1, 1-25, (2000) · Zbl 0962.68086
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.