7
$\begingroup$

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.

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

1 Answer 1

9
$\begingroup$

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$.

$\endgroup$
5
  • $\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$ Jul 30, 2014 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, 2014 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, 2014 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, 2014 at 20:12
  • 1
    $\begingroup$ @jmite If you bound $\Sigma$, yes. (As Yuval noted.) $\endgroup$
    – Raphael
    Jul 30, 2014 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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