Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for all $i$ such that $v_{k_1}v_{k_2}...=w_{k_1}w_{k_2}...$? It seems that undecidability of the original Post Correspondence problem should imply there is no such algorithm. Is there a reference that shows undecidability of this variation of Post? Thanks.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
5
|
|
|||||
|
|
3
|
See Halava, Vesa, Harju, Tero, Karhumäki, Juhani Decidability of the binary infinite Post correspondence problem. If the alphabet consists of $\le 2$ letters, then the problem is decidable, if the number of letters is at least 7, then the problem is undecidable. The latter result is proved in Y. Matiyasevich, G. Sénizergues, Decision problems for semi-Thue systems with a few rules, in: Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, NJ, 27–30 July 1996, IEEE Computer Society, Silver Spring, MD, pp. 523–531. |
|||
|
