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

CC BY-SA 3.0
2016-07-27T00:02:13.920Z
Have a look at the [Sardinas–Patterson algorithm](https://en.wikipedia.org/wiki/Sardinas%E2%80%93Patterson_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
CC BY-SA 3.0
2016-07-04T07:58:51.367Z
2016-07-04T07:58:51.367Z
Matei
<p>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}$.</p>

<p>Now consider an apparently similar problem:
Given <strong>distinct</strong> words $w_1, \ldots, w_n$, there exist two <strong>distinct</strong> 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$. </p>

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

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

<p>Is my problem standard? Is it undecidable?</p>

CC BY-SA 3.0
2016-06-29T21:41:05.903Z
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
CC BY-SA 3.0
2016-06-30T16:09:08.460Z
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
<undecidability><complexity><post-correspondence>
A variant of the Post Correspondence problem
Matei
# A variant of the Post Correspondence problem

(Asked by: username_0 on 2016-06-29)

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?

**Tags:** undecidability, complexity, post-correspondence

> **Comments:**
> **username_1**: 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  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_0 on 2016-07-04. Score: 0 | Accepted answer

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

> **Comments:**
> **username_2**: Have a look at the [Sardinas–Patterson algorithm](https://en.wikipedia.org/wiki/Sardinas%E2%80%93Patterson_algorithm) for deciding unique decodability of variable length codes. Wikipedia quotes $O(mk)$ complexity, where $m$ and $k$ are as in your answer.  

---

