Some undecidable termination problems for semi-Thue systems. (English) Zbl 0873.68054
Summary: We show that the uniform termination problem is undecidable for length-preserving semi-Thue systems having 9 rules. We then give an explicit uniformly terminating semi-Thue system \({\mathcal T}\) having 9 rules which is “universal with respect to termination problems” in some sense. It follows that there exists a fixed rule \((u_{0}, v_{0})\) such that \({\mathcal T}\cup {(u_{0}, v_{0})}\) has 10 rules and undecidable termination problem.
MSC:
| 68Q42 | Grammars and rewriting systems |
| 03D03 | Thue and Post systems, etc. |
| 03D35 | Undecidability and degrees of sets of sentences |
Keywords:
semi-Thue systemReferences:
| [1] | Billaud, M.; Lafon, P.; Métivier, Y.; Sopena, E., Graph rewriting systems with priorities, (Proc. WG 89, 411 (1989), Springer: Springer Berlin), 94-106, Lecture Notes in Computer Science · Zbl 0768.68120 |
| [2] | Book, R. V., Homogeneous Thue systems and the Church—Rosser property, Discrete Math., 137-145 (1984) · Zbl 0546.03019 |
| [3] | Book, R. V.; Otto, F., Cancellation rules and extended word problems, Inform. Process. Lett., 20, 5-11 (1985) · Zbl 0561.68030 |
| [4] | Book, R. V.; Otto, F., String Rewriting Systems. Texts and monographs in Computer Science (1993), Springer: Springer Berlin · Zbl 0832.68061 |
| [5] | Boone, W. W.; Collins, D.; Matiyasevich, Y. V., Embedding into semi-groups with only a few defining relations, (Proc. 2nd Scandinavian Logic Symp. Studies in Logic and the foundations of Mathematics (1971), North-Holland: North-Holland Amsterdam), 27-40 · Zbl 0228.20029 |
| [6] | Borisov, V. V., Simple examples of groups with unsolvabe word problem, Math. Notes, 6, 521-532 (1969), an English translation appears in · Zbl 0211.34102 |
| [7] | Bossut, F.; Dauchet, M.; Warin, B., Automata and rational expressions on planar graphs, Lecture Notes in Computer Science (1988), Springer: Springer Berlin · Zbl 0656.68079 |
| [8] | Caron, A. C., Linear bounded automata and rewrite systems: influence of initial configurations on decision properties, Proc. CAAP 91 (1991), Springer: Springer Berlin, Lecture Notes in Computer Science · Zbl 0967.68523 |
| [9] | Ceitin, G. S., An associative calculus with an insoluble problem of equivalence, Trudy Mat. Inst. Steklov., 52, 172-189 (1952) · Zbl 0087.25303 |
| [10] | 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 |
| [11] | Collins, D. J., A. simple presentation of a group with unsolvable word problem, Illinois J. Math., 30, 2, 230-234 (1986) · Zbl 0571.20027 |
| [12] | Dauchet, M., Simulation of Turing machines by a left-linear rewrite rule, (Proc. RTA 89, 355 (189), Springer: Springer Berlin), 109-120, Lecture Notes in Computer Science · Zbl 1503.68067 |
| [13] | Davis, M., Computability and Unsolvability (1958), McGraw-Hill: McGraw-Hill New York · Zbl 0080.00902 |
| [14] | Dershowitz, N., Termination of rewriting, J. Symbolic Comput., 3, 69-116 (1987) · Zbl 0637.68035 |
| [15] | Dershowitz, N.; Jouannaud, J. P., Rewrite sysrtems, (Handbook of Theoretical Computer Science, B (1991), Elsevier: Elsevier Amsterdam), 243-320, Ch. 2 · Zbl 0900.68283 |
| [16] | Hooper, P. K., The undecidability of the Turing machine immortality problem, J. Symbolic Logic, 31, 2, 219-234 (1966) · Zbl 0173.01201 |
| [17] | Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. ACM, 27, 4, 797-821 (1980) · Zbl 0458.68007 |
| [18] | Huet, G.; Lankford, D., On the uniform halting problem for term rewriting systems (1978), Rapport Laboria |
| [19] | Jantzen, M., Confluent String Rewriting (EATCS monograph) (1988), Springer: Springer Berlin · Zbl 1097.68572 |
| [20] | König, D., Theorie der Endlichen und Unendlichen Graphen (1950), Chelsea, New York · Zbl 0040.10303 |
| [21] | Matiyasevich, J. V., Simple examples of undecidable associative calculi, Soviet Math. Dokl., 555-557 (1967) · Zbl 0189.01102 |
| [22] | Matiyasevich, Y., Word problem for Thue systems with a few relations, (Actes de l’école de printemps d’informatique théorique, Font-Romeu (1994), Springer: Springer Berlin), 93 |
| [23] | Pansiot, J. J., A note on Post’s correspondence problem, IPL, 12, 233 (1981) · Zbl 0485.03018 |
| [24] | Rogers, H. J., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill · Zbl 0183.01401 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
