Given words $\alpha_1, \ldots \alpha_n$ and $\beta_1, \ldots, \beta_n$, Post's Correspondence Problem asks if there is a sequence $i_1, \ldots, i_k$ of indices such that $\alpha_{i_1} \ldots \alpha_{i_k} = \beta_{i_1} \ldots \beta_{i_k}$.

Now consider an apparently similar problem: Given distinct words $w_1, \ldots, w_n$, there exist two distinct sequences $i_1, \ldots, i_m$ and $j_1, \ldots j_k$ such that $w_{i_1} \ldots w_{i_m} = w_{j_1} \ldots w_{j_k}$? There is no restriction on the values $k$ and $m$.

Intuitively, the problem attempts see if there exists a word which can be constructed in two different ways via concatenation, using word fragments $w_1, \ldots w_n$.

I have unsuccessfully tried to reduce PCP to this problem. (...and I'm not sure if its fair to call this a variant of PCP anyway).

Is my problem standard? Is it undecidable?

  • $\begingroup$ I think you can rephrase your question in terms of CFGs and ambiguity, in which case: cstheory.stackexchange.com/questions/4352/… $\endgroup$ – JimN Jun 29 '16 at 21:41
  • $\begingroup$ Hello, thanks for the comment ! Indeed it seems that my problem is a case of CFG ambiguity, however it seems to be a strictly particular case. I'm not sure if I could use an oracle for my problem to solve CFG ambiguity. So undecidability (for my problem) is still an open issue. $\endgroup$ – user3383312 Jun 30 '16 at 16:09

It turns out that the problem is decidable in polynomial time ($O(m^2\cdot k)$, where $m$ is the sum of lengths of all words and $k$ is the size of the alphabet).

| cite | improve this answer | |
  • $\begingroup$ Have a look at the Sardinas–Patterson algorithm for deciding unique decodability of variable length codes. Wikipedia quotes $O(mk)$ complexity, where $m$ and $k$ are as in your answer. $\endgroup$ – Hendrik Jan Jul 27 '16 at 0:02

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.