A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem

• Autorzy: Halava V. , Harju T. , Sahla E.

Identyfikatory

DOI

10.3233/FI-2017-1558

• Języki publikacji: EN

Abstrakty

EN

We give a new simplified proof for undecidability of the Bi-Infinite Post Correspondence Problem (ℤPCP). We reduce the special case of the word problem of semi-Thue systems to ℤPCP.

Słowa kluczowe

EN

infinity; correspondence analysis; finite groups; combinatorial analysis; algebra

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 167--176
• Opis fizyczny: Bibliogr. 21 poz., tab.

Twórcy

autor

Halava V.

• Department of Mathematics and Statistics, University of Turku, Finland

autor

Harju T.

• Department of Mathematics and Statistics, University of Turku, Finland

autor

Sahla E.

• Department of Mathematics and Statistics, University of Turku, Finland

Bibliografia

• [1] Post EL. A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc., 1946;52:264–268. doi:10.1090/S0002-9904-1946-08555-9. URL http://dx.doi.org/10.1090/S0002-9904-1946-08555-9.
• [2] Markoff A. On the impossibility of certain algorithms in the theory of associative systems. C. R. (Doklady) Acad. Sci. URSS (N.S.), 1947;55:583–586.
• [3] Post EL. Recursive unsolvability of a problem of Thue. J. Symbolic Logic, 1947;12:1–11. doi:10.2307/2267170. URL http://dx.doi.org/10.2307/2267170.
• [4] Ehrenfeucht A, Karhumäki J, Rozenberg G. The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci., 1982;21(2):119–144. doi:10.1016/0304-3975(89)90080-7. URL http://dx.doi.org/10.1016/0304- 3975(89)90080-7.
• [5] Halava V, Harju T, Hirvensalo M. Binary (generalized) Post correspondence problem. Theoret. Comput. Sci., 2002;276(1-2):183–204. doi:10.1016/S0304-3975(01)00157-8. URL http://dx.doi.org/10.1016/S0304-3975(01)00157-8.
• [6] Neary T. Undecidability in binary tag systems and the Post correspondence problem for five pairs of words. In: 32nd International Symposium on Theoretical Aspects of Computer Science, volume 30 of LIPIcs. Leibniz Int. Proc. Inform., pp. 649–661. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015.
• [7] Dong J, Liu Q. Undecidability of infinite Post correspondence problem for instances of size 8. RAIRO Theor. Inform. Appl., 2012;46(3):451–457. doi:10.1051/ita/2012015.
• [8] Finkel O. The exact complexity of the infinite Post correspondence problem. Inform. Process. Lett., 2015;115(6-8):609–611. doi:10.1016/j.ipl.2015.02.009. URL http://dx.doi.org/10.1016/j.ipl.2015.02.009.
• [9] Halava V, Harju T, Karhumäki J. Decidability of the binary infinite Post correspondence problem. Discrete Appl. Math., 2003;130(3):521–526. doi:10.1016/S0166-218X(03)00330-5. URL http://dx.doi.org/10.1016/S0166-218X(03)00330-5.
• [10] Ruohonen K. On some variants of Post’s correspondence problem. Acta Inform., 1983;19(4):357–367. doi:10.1007/BF00290732. URL http://dx.doi.org/10.1007/BF00290732.
• [11] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
• [12] Post EL. Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc., 1944;50:284–316. doi:10.1090/S0002-9904-1944-08111-1. URL http://dx.doi.org/10.1090/S0002-9904-1944-08111-1.
• [13] Church A. Review: Formal Reductions of the General Combinatorial Decision Problem by Emil L. Post. The Journal of Symbolic Logic, 1943;8(02):50. doi:10.2307/2268006.
• [14] Post EL. Formal reductions of the general combinatorial decision problem. Amer. J. Math., 1943;65:197–215. doi:10.2307/2371809. URL http://dx.doi.org/10.2307/2371809.
• [15] Post EL. In M. Davis (ed), The undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions., chapter Absolutely unsolvable problems and relatively undecidable propositions. Account of an anticipation., pp. 340–433. Raven Press, Hewlett, N.Y., 1965.
• [16] Matiyasevich Y, Sénizergues G. Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci., 2005;330(1):145–169. doi:10.1016/j.tcs.2004.09.016. URL http://dx.doi.org/10.1016/j.tcs.2004.09.016.
• [17] Claus V. Some remarks on PCP(k) and related problems. Bull. EATCS, 1980;12:54–61.
• [18] Halava V, Harju T. Undecidability of infinite Post correspondence problem for instances of Size 9. RAIRO Theor. Inform. Appl., 2006;40(4):551–557. doi:10.1051/ita:2006039.
• [19] Halava V, Harju T. New proof for the undecidability of the circular PCP. Acta Inform., 2013;50(5-6):331–341. doi:10.1007/s00236-013-0183-5. URL http://dx.doi.org/10.1007/s00236-013-0183-5.
• [20] Halava V, Harju T. Word problem for deterministic and reversible semi-Thue systems. Semigroup Forum, 2014;88(2):468–478. doi:10.1007/s00233-013-9550-3. URL http://dx.doi.org/10.1007/s00233-013-9550-3.
• [21] Huet G, Lankford D. On the uniform halting problem for term rewriting systems. Rapport Laboria 283, INRIA, 1978. URL http://www.ens-lyon.fr/LIP/REWRITING/TERMINATION/Huet_Lankford.pdf.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).