# Post Correspondence Problem variant

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!

• 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). Jan 12 '11 at 23:11

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.

• welcome to cstheory ! Jan 13 '11 at 22:11
• Awesome! Now we just need Eric Bach... Jan 14 '11 at 0:03
• Nice! That's perfect. Jan 14 '11 at 17: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).

• Agh--indeed! Sorry about that, you're absolutely right. Jan 12 '11 at 19:19
• What if we restrict $K = K'$? Jan 12 '11 at 20:11
• 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. Jan 14 '11 at 15:43
• My comment above is only for the original problem, not the problem where $K = K'$. Jan 14 '11 at 18:10