3
$\begingroup$

Given two ordered sets of words $a_1, a_2, ..., a_k$, $b_1, b_2, ..., b_k$ taking values in some discrete alphabet $A$, a solution to the PCP problem is a sequence $i_1, ..., i_n$ taking values in $1, 2,..., k$ such that $a_{i_1}|a_{i_2}|...|a_{i_n}=b_{i_1}|b_{i_2}|...|b_{i_n}$ where $|$ means concatenation. $k$ can be called the length of the problem, $n$ the length of the solution and if we let $w$ be the length of the largest word in $a_1, a_2, ..., a_k, b_1, b_2, ..., b_k$, $w$ is called the width of the problem.

I know that the PCP problem becomes decidable in several scenarios, for instance: for bounded $n$, or if $A$ is unary, etc. On the other hand for $k\geq7$ PCP is still undecidable. My question is, is there any result known for bounded values of $w$?

$\endgroup$
1
  • 1
    $\begingroup$ You may be interested in this question. $\endgroup$
    – Raphael
    Nov 13, 2013 at 22:10

1 Answer 1

3
$\begingroup$

If $w$ is bounded, and the alphabet size is bounded, then the number of possible words is bounded. Thus, there is only a finite number of possible instances, so the problem becomes a finite languages, and hence decidable.

If you don't bound the alphabet, then you can encode any width of $w$ by adding more letters, so the problem is the same as standard PCP, and hence undecidable.

$\endgroup$
2
  • $\begingroup$ Yes, maybe my argument is flawed. What I was thinking about is that still with $w$ fixed which limits the length of the ---input--- word and $k$ fixed; the number of words is unlimited since there are infinite ways of combining them. Note that $n$ would be unbounded... $\endgroup$
    – Al Learner
    Oct 23, 2013 at 9:49
  • 1
    $\begingroup$ $n$ is unbounded, but that doesn't matter: suppose you only have 1000 possible instances of PCP. Then you have at most a 1000 "yes" instances, and the rest are "no", so the language is finite. $\endgroup$
    – Shaull
    Oct 23, 2013 at 10:00

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.