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

Halava, V.; Harju, T.; Sahla, E.

doi:10.3233/FI-2017-1558

Artykuł - szczegóły

Tytuł artykułu

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

Autorzy

Halava V. , Harju T. , Sahla E.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

DOI

10.3233/FI-2017-1558

Warianty tytułu

Języki publikacji

Abstrakty

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

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.

vesa.halava@utu.fi

Department of Mathematics and Statistics, University of Turku, Finland

autor

Harju T.

harju@utu.fi

Department of Mathematics and Statistics, University of Turku, Finland

autor

Sahla E.

estasa}@utu.fi

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).

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-8f28ec57-3707-446b-b851-136e5fdc9a3e