MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
According to this abstract, 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. – John Stillwell Oct 18 '10 at 23:11
up vote 5 down vote accepted

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.

share|cite|improve this answer
Thank you for the reference. – jim Oct 19 '10 at 1:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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