<p>Edit: This solves an earlier version, in which we have to decide whether there is an equality of the form $\alpha_{i_1} \cdots \alpha_{i_K} = \beta_{j_1} \cdots \beta_{j_{K&#39;}}$. The new version has $K = K&#39;$.</p>

<p>The language $A$ generated by all strings of the form $\alpha_{i_1} \cdots \alpha_{i_K}$ is regular. The language $B$ generated by all strings of the form $\beta_{j_1} \cdots \beta_{j_{K&#39;}}$ is regular. You're asking whether $A \cap B$ is empty. Since $A,B$ are regular, this is decidable (in fact, in at most exponential time).</p>

CC BY-SA 2.5
2011-01-12T19:19:37.487Z
Agh--indeed! Sorry about that, you're absolutely right.
alpoge
CC BY-SA 2.5
2011-01-12T20:11:57.990Z
What if we restrict $K = K'$?
alpoge
CC BY-SA 2.5
2011-01-14T15:43:21.127Z
You can do it in polynomial time.  Make a trie $T_1$ for the words of the first set A, and a trie $T_2$ for the words of the second set B.  These tries are essentially NFA's.  From these, create NFA's for $T_1^+$ and $T_2^+$ using the usual construction.  Now, using the usual cross-product construction, make an NFA $M$ for their intersection.  The emptiness of the language accepted by M can now be checked through the usual path-finding DFS approach.
Jeffrey Shallit
CC BY-SA 2.5
2011-01-14T18:10:11.180Z
My comment above is only for the original problem, not the problem where $K = K'$.
Jeffrey Shallit
CC BY-SA 2.5
2011-01-12T19:04:43.533Z
2011-01-13T05:54:27.033Z
2011-01-13T05:54:27.033Z
Yuval Filmus
<p>This new version - where $K = K&#39;$ - is decidable.</p>

<p>Let's show that the language $L := \bigcup_{k \geq 1} (A^k \ \cap \ B^k)$ is a CFL.  Then the decidability follows from the decidability of the emptiness of a CFL.</p>

<p>We'll design a PDA to accept $L$.  On input $x$, this PDA will try to construct two factorizations of $x$, one using words of $A$, and the other using words of $B$.  It will use a counter on the stack to ensure these two factorizations are of the same length.  Conceptually I will refer to the $A$-factorization of $x$ so far as sitting on top of $x$ and the $B$-factorization as sitting on the bottom of $x$.  Then the stack will contain $n$ counters iff the absolute value of the difference of the number of words matched on the top, minus the number of words on the bottom, is $n$.  We need another state of the PDA to record what the appropriate sign is corresponding to $n$ (which tells us if the $A$-factorization is longer than the $B$-factorization, or vice versa).</p>

<p>As we scan the letters of $x$, we nondeterministically guess a word $t$ of $A$ and a word $u$ of $B$ to which this letter begins.  Once we guess, we are committed to matching the rest of $t$ and $u$ against $x$; if at any point our match fails, we halt in this nondeterministic choice.  So we also maintain, in the state of our PDA, the suffix of $t$ and $u$ that remains to match.</p>

<p>As we scan further letters, we continue matching until we hit the end of $t$ or the end of $u$ (or both).  When we hit the end of a word, we update the stack appropriately, and then guess a new word to match in either the top or bottom (or both).</p>

<p>We accept if the suffixes remaining to be matched are both empty in top and bottom, and the stack contains no counters.  </p>

<p>We can construct this PDA effectively, so we can effectively decide if it accepts anything or not (for example, by converting effectively to a grammar $G$ and then using the usual method to see if G generates anything).</p>

<p>Edit: One can also turn this into an upper bound on how big $k$ can be, in the worst case.  I think it should give an upper bound of something roughly like $2^{O(l^2)}$, where $l$ is the sum of the lengths of the words in $A$ and $B$.</p>

<p>Edit: I see now that the requirement that $A$ and $B$ be finite sets can also be relaxed, to the requirement that $A$ and $B$ be regular (possibly infinite).  In this case, instead of maintaining the suffix remaining to be matched in "top" and "bottom", instead we maintain the states of the respective DFA we are in, after processing the prefix of a possible matched word.  If we hit a final state in either "top" or "bottom", we can nondeterministically choose to go back to the initial state for a new guessed word.  </p>

CC BY-SA 2.5
2011-01-13T22:11:58.490Z
welcome to cstheory !
Suresh Venkat
CC BY-SA 2.5
2011-01-14T00:03:33.363Z
Awesome! Now we just need Eric Bach...
Huck Bennett
CC BY-SA 2.5
2011-01-14T17:13:49.563Z
Nice! That's perfect.
alpoge
CC BY-SA 2.5
2011-01-13T21:46:26.093Z
2011-01-13T22:46:41.900Z
2011-01-13T22:46:41.900Z
Jeffrey Shallit
<p>This is probably pretty simple, but consider the standard Post Correspondence Problem:</p>

<p>Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find a sequence of indices $i_1, \ldots, i_K$ such that $\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{i_1}\cdots \beta_{i_K}$. This is, of course, undecidable.</p>

<p>Now, I call this a 'variant', but it's not really--it essentially throws away 'correspondence'. Anyway, consider the following variant:</p>

<p>Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find <i>two</i> sequences of indices $i_1, \ldots, i_K, j_1, \ldots, j_{K}$ such that $\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{j_1}\cdots \beta_{j_{K}}$. What can be said about this variant? If this is trivial, my apologies!</p>

CC BY-SA 2.5
2011-01-12T23:11:45.643Z
Without asking a brand new question, I'm editing the condition that $K$ and $K'$ are not necessarily equal. In the case where they are equal, the problem should probably be undecidable--however a reduction is not obvious (to me).
alpoge
<computability><fl.formal-languages>
Post Correspondence Problem variant
alpoge
# Post Correspondence Problem variant

(Asked by: username_0 on 2011-01-12)

This is probably pretty simple, but consider the standard Post Correspondence Problem:

Given $\alpha\_1, \ldots, \alpha\_N$ and $\beta\_1, \ldots, \beta\_N$, find a sequence of indices $i\_1, \ldots, i\_K$ such that $\alpha\_{i\_1}\cdots \alpha\_{i\_K} = \beta\_{i\_1}\cdots \beta\_{i\_K}$. This is, of course, undecidable.

Now, I call this a 'variant', but it's not really--it essentially throws away 'correspondence'. Anyway, consider the following variant:

Given $\alpha\_1, \ldots, \alpha\_N$ and $\beta\_1, \ldots, \beta\_N$, find *two* sequences of indices $i\_1, \ldots, i\_K, j\_1, \ldots, j\_{K}$ such that $\alpha\_{i\_1}\cdots \alpha\_{i\_K} = \beta\_{j\_1}\cdots \beta\_{j\_{K}}$. What can be said about this variant? If this is trivial, my apologies!

**Tags:** computability, fl.formal-languages

> **Comments:**
> **username_0**: Without asking a brand new question, I'm editing the condition that $K$ and $K'$ are not necessarily equal. In the case where they are equal, the problem should probably be undecidable--however a reduction is not obvious (to me).  

---

## 2 answers

### Answer by username_2 on 2011-01-13. Score: 18 | Accepted answer

This new version - where $K = K'$ - is decidable.

Let's show that the language $L := \bigcup\_{k \geq 1} (A^k \ \cap \ B^k)$ is a CFL. Then the decidability follows from the decidability of the emptiness of a CFL.

We'll design a PDA to accept $L$. On input $x$, this PDA will try to construct two factorizations of $x$, one using words of $A$, and the other using words of $B$. It will use a counter on the stack to ensure these two factorizations are of the same length. Conceptually I will refer to the $A$-factorization of $x$ so far as sitting on top of $x$ and the $B$-factorization as sitting on the bottom of $x$. Then the stack will contain $n$ counters iff the absolute value of the difference of the number of words matched on the top, minus the number of words on the bottom, is $n$. We need another state of the PDA to record what the appropriate sign is corresponding to $n$ (which tells us if the $A$-factorization is longer than the $B$-factorization, or vice versa).

As we scan the letters of $x$, we nondeterministically guess a word $t$ of $A$ and a word $u$ of $B$ to which this letter begins. Once we guess, we are committed to matching the rest of $t$ and $u$ against $x$; if at any point our match fails, we halt in this nondeterministic choice. So we also maintain, in the state of our PDA, the suffix of $t$ and $u$ that remains to match.

As we scan further letters, we continue matching until we hit the end of $t$ or the end of $u$ (or both). When we hit the end of a word, we update the stack appropriately, and then guess a new word to match in either the top or bottom (or both).

We accept if the suffixes remaining to be matched are both empty in top and bottom, and the stack contains no counters.

We can construct this PDA effectively, so we can effectively decide if it accepts anything or not (for example, by converting effectively to a grammar $G$ and then using the usual method to see if G generates anything).

Edit: One can also turn this into an upper bound on how big $k$ can be, in the worst case. I think it should give an upper bound of something roughly like $2^{O(l^2)}$, where $l$ is the sum of the lengths of the words in $A$ and $B$.

Edit: I see now that the requirement that $A$ and $B$ be finite sets can also be relaxed, to the requirement that $A$ and $B$ be regular (possibly infinite). In this case, instead of maintaining the suffix remaining to be matched in "top" and "bottom", instead we maintain the states of the respective DFA we are in, after processing the prefix of a possible matched word. If we hit a final state in either "top" or "bottom", we can nondeterministically choose to go back to the initial state for a new guessed word.

> **Comments:**
> **username_3**: welcome to cstheory !  
> **username_4**: Awesome! Now we just need Eric Bach...  
> **username_0**: Nice! That's perfect.  

---

### Answer by username_1 on 2011-01-12. Score: 13

Edit: This solves an earlier version, in which we have to decide whether there is an equality of the form $\alpha\_{i\_1} \cdots \alpha\_{i\_K} = \beta\_{j\_1} \cdots \beta\_{j\_{K'}}$. The new version has $K = K'$.

The language $A$ generated by all strings of the form $\alpha\_{i\_1} \cdots \alpha\_{i\_K}$ is regular. The language $B$ generated by all strings of the form $\beta\_{j\_1} \cdots \beta\_{j\_{K'}}$ is regular. You're asking whether $A \cap B$ is empty. Since $A,B$ are regular, this is decidable (in fact, in at most exponential time).

> **Comments:**
> **username_0**: Agh--indeed! Sorry about that, you're absolutely right.  
> **username_0**: What if we restrict $K = K'$?  
> **username_2**: You can do it in polynomial time.  Make a trie $T_1$ for the words of the first set A, and a trie $T_2$ for the words of the second set B.  These tries are essentially NFA's.  From these, create NFA's for $T_1^+$ and $T_2^+$ using the usual construction.  Now, using the usual cross-product construction, make an NFA $M$ for their intersection.  The emptiness of the language accepted by M can now be checked through the usual path-finding DFS approach.  
> **username_2**: My comment above is only for the original problem, not the problem where $K = K'$.  

---

