# Undecidability of infinite post correspondence problem for instances of Size 9

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 4, page 551-557
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHalava, Vesa, and Harju, Tero. "Undecidability of infinite post correspondence problem for instances of Size 9." RAIRO - Theoretical Informatics and Applications 40.4 (2006): 551-557. <http://eudml.org/doc/249719>.

@article{Halava2006,

abstract = {
In the infinite Post Correspondence Problem an instance (h,g)
consists of two morphisms h and g, and the problem is to
determine whether or not there exists an infinite word ω
such that h(ω) = g(ω). 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.
},

author = {Halava, Vesa, Harju, Tero},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Infinite Post Correspondence Problem; undecidability;
word problem; semi–Thue system.; Post correspondence problem},

language = {eng},

month = {11},

number = {4},

pages = {551-557},

publisher = {EDP Sciences},

title = {Undecidability of infinite post correspondence problem for instances of Size 9},

url = {http://eudml.org/doc/249719},

volume = {40},

year = {2006},

}

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

DA - 2006/11//

PB - EDP Sciences

VL - 40

IS - 4

SP - 551

EP - 557

AB -
In the infinite Post Correspondence Problem an instance (h,g)
consists of two morphisms h and g, and the problem is to
determine whether or not there exists an infinite word ω
such that h(ω) = g(ω). 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.

LA - eng

KW - Infinite Post Correspondence Problem; undecidability;
word problem; semi–Thue system.; Post correspondence problem

UR - http://eudml.org/doc/249719

ER -

## References

top- V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theory Comput. Syst.36 (2003) 231–245. Zbl1039.68061
- V. Claus, Some remarks on PCP(k) and related problems. Bull. EATCS12 (1980) 54–61.
- A. Ehrenfeucht, J. Karhumäki and G. Rozenberg, The (generalized) Post Correspondence Problem with lists consisting of two words is decidable. Theoret. Comput. Sci.21 (1982) 119–144. Zbl0493.68076
- V. Halava and T. Harju, 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. Zbl1060.03068
- V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post Correspondence Problem. Theoret. Comput. Sci.276 (2002) 183–204. Zbl1023.03038
- V. Halava, T. Harju and J. Karhumäki, Decidability of the binary infinite Post Correspondence Problem. Discrete Appl. Math.130 (2003) 521–526. Zbl1023.03039
- T. Harju and J. Karhumäki, Morphisms, in Handbook of Formal Languages, volume 1, edited by G. Rozenberg and A. Salomaa, Springer-Verlag (1997) 439–510.
- T. Harju, J. Karhumäki and D. Krob, Remarks on generalized Post correspondence problem, in STACS'96, edited by C. Puech and R. Reischuk. Lect. Notes Comput. Sci.1046 (1996) 39–48.
- Y. Matiyasevich and G. Sénizergues, Decision problems for semi–Thue systems with a few rules. Theor. Comput. Sci.330 (2005) 145–169. Zbl1078.03033
- E. Post, A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc.52 (1946) 264–268. Zbl0063.06329
- K. Ruohonen, Reversible machines and Post's correspondence problem for biprefix morphisms. J. Inform. Process. Cybernet. EIK 21 (1985) 579–595. Zbl0604.68057

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.