In the infinite Post Correspondence Problem an instance consists of two morphisms and , and the problem is to determine whether or not there exists an infinite word such that . This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini (Theory Comput. Syst. 36 (2003) 231-245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable for instances where the morphisms have domains of 9 letters. The proof uses a recent result of Matiyasevich and Sénizergues and a modification of a result of Claus.
Mots clés : infinite post correspondence problem, undecidability, word problem, semi-Thue system
@article{ITA_2006__40_4_551_0,
author = {Halava, Vesa and Harju, Tero},
title = {Undecidability of infinite post correspondence problem for instances of size 9},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {551--557},
publisher = {EDP-Sciences},
volume = {40},
number = {4},
year = {2006},
doi = {10.1051/ita:2006039},
mrnumber = {2277048},
zbl = {1114.03035},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2006039/}
}
TY - JOUR AU - Halava, Vesa AU - Harju, Tero TI - Undecidability of infinite post correspondence problem for instances of size 9 JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 551 EP - 557 VL - 40 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006039/ DO - 10.1051/ita:2006039 LA - en ID - ITA_2006__40_4_551_0 ER -
%0 Journal Article %A Halava, Vesa %A Harju, Tero %T Undecidability of infinite post correspondence problem for instances of size 9 %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 551-557 %V 40 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006039/ %R 10.1051/ita:2006039 %G en %F ITA_2006__40_4_551_0
Halava, Vesa; Harju, Tero. Undecidability of infinite post correspondence problem for instances of size 9. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 551-557. doi : 10.1051/ita:2006039. http://www.numdam.org/articles/10.1051/ita:2006039/
[1] and, Undecidable problems for probabilistic automata of fixed dimension. Theory Comput. Syst. 36 (2003) 231-245. | Zbl
[2] , Some remarks on PCP(k) and related problems. Bull. EATCS 12 (1980) 54-61.
[3] , and, The (generalized) Post Correspondence Problem with lists consisting of two words is decidable. Theoret. Comput. Sci. 21 (1982) 119-144. | Zbl
[4] and, Infinite solutions of the marked Post Correspondence Problem, in Formal and Natural Computing, edited by J. Karhumäki, W. Brauer, H. Ehrig and A. Salomaa. Lecture Notes in Comput. Sci. 2300 (2002) 57-68. | Zbl
[5] , and, Binary (generalized) Post Correspondence Problem. Theoret. Comput. Sci. 276 (2002) 183-204. | Zbl
[6] , and, Decidability of the binary infinite Post Correspondence Problem. Discrete Appl. Math. 130 (2003) 521-526. | Zbl
[7] and, Morphisms, in Handbook of Formal Languages, volume 1, edited by G. Rozenberg and A. Salomaa, Springer-Verlag (1997) 439-510.
[8] , and, Remarks on generalized Post correspondence problem, in STACS'96, edited by C. Puech and R. Reischuk. Lect. Notes Comput. Sci. 1046 (1996) 39-48.
[9] and, Decision problems for semi-Thue systems with a few rules. Theor. Comput. Sci. 330 (2005) 145-169. | Zbl
[10] , A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946) 264-268. | Zbl
[11] , Reversible machines and Post's correspondence problem for biprefix morphisms. J. Inform. Process. Cybernet. EIK 21 (1985) 579-595. | Zbl
Cité par Sources :
