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.

  • 1
    $\begingroup$ According to this abstract, springerlink.com/content/x92705867jnu247w the Post correspondence problem is undecidable for doubly infinite words. This not quite what you want, but perhaps the method can be adapted to your problem. $\endgroup$ – John Stillwell Oct 18 '10 at 23:11

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.