So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$.

I'm wondering, can anything similar be said for when there is a fixed word length?

To be precise, here's the problem:

Given fixed $m$ and $n$, with $n \geq 7$, and words $u_1, \ldots u_n$ and $v_1 \ldots v_n$ such that $|u_i| \leq m$ and $|v_i| \leq m$, is there an index sequence $i_1, \ldots i_k$ such that $u_{i_1} \cdots u_{i_k} = v_{i_1} \cdots v_{i_k}$.

For what values of $m$, if any, is this known to be undecidable?

Note that this is similar to this question, but none of the 8 linked papers seemed by their titles to answer my question, and I haven't fully read all 8 of them yet.

  • 5
    $\begingroup$ There is another parameter, the target alphabet size. This has to be unbounded since otherwise your problem is trivially decidable. $\endgroup$ – Yuval Filmus Jul 29 '14 at 22:47

For all $m \geq 3$, the problem is undecidable.

Proof by reduction from the word problem of unrestricted grammars:

  1. Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have length at most $3$.

    This can be seen by translating any grammar into an equivalent TM and then converting back.

  2. Map the resulting grammar to PCP instances; no tile is longer than the longest left or right side of a rule.

    That is, with step 1, all tiles have length $\geq 3$.

  • $\begingroup$ That is: bound on world length $m$, but no bound on number of words $n$. The question seems to look for bounds on both, but see comment by Yuval. (nevertheless +1) $\endgroup$ – Hendrik Jan Jul 30 '14 at 9:39
  • $\begingroup$ @HendrikJan Hm, true, missed that ("fixed $n$"). I wonder how to go about that; maybe via a small universal TM? $\endgroup$ – Raphael Jul 30 '14 at 9:42
  • $\begingroup$ Originally I was looking for fixed $m$ and $n$, but this is still a very interesting result regardless! $\endgroup$ – jmite Jul 30 '14 at 17:53
  • $\begingroup$ Actually, now that I think about it, it's really weird if you have fixed $m$ and $n$ since technically then you're dealing with a finite, therefore regular, language. There probably is no algorithm which can generate a description of that language (RE, DFA etc.) since you'd need to solve each PCP instance, but there is a finite number of instances with fixed $m$ and $n$. $\endgroup$ – jmite Jul 30 '14 at 20:12
  • 1
    $\begingroup$ @jmite If you bound $\Sigma$, yes. (As Yuval noted.) $\endgroup$ – Raphael Jul 30 '14 at 20:39

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.