Post Correspondence Problem variant

Question

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!

Answer 1

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.

Answer 2

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