A variant of the Post Correspondence problem

Question

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?

I think you can rephrase your question in terms of CFGs and ambiguity, in which case: http://cstheory.stackexchange.com/questions/4352/how-is-proving-a-context-free-language-to-be-ambiguous-undecidable — JimN, Jun 29 '16 at 21:41
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. — Matei, Jun 30 '16 at 16:09

score 0 · Accepted Answer · answered Jul 04 '16 at 07:58

0

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

answered Jul 04 '16 at 07:58

Matei

1
1

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. – Hendrik Jan Jul 27 '16 at 00:02

A variant of the Post Correspondence problem

1 Answers1