For a fixed language $L$ on some alphabet $A$, let us consider the following problem, that I call $L$-INTERLEAVING:
- Input: two words $u, v \in A^*$
- Output: whether there exists an interleaving of $u$ and $v$ which is in $L$.
Here, an interleaving of two words $u$ and $v$ is a word $w$ that can be obtained intuitively by taking the letters of $u$ and $v$ while keeping their relative order. Formally, $w$ is an interleaving of $u$ and $v$ if we can partition it into two disjoint subsequences, one which is equal to $u$ and the other which is equal to $v$. For instance, "bheleloll" is an interleaving of "hello" and "bell".
What is the complexity of the $L$-INTERLEAVING problem, depending on the language $L$? In particular:
- If $L$ is regular, then we can solve the problem with a dynamic algorithm on the two strings which shows it to be in the class NL. Is it NL-hard for some regular languages? However, for some regular languages, the problem is clearly in L (deterministic logspace). Is there some characterization of the languages for which the problem is in L?
- If $L$ is not regular, the problem is still in NL when $L$ has polynomial online deterministic space complexity (see here for this notion, or my earlier question). However, this does not cover, e.g., all context-free languages; yet, some others (e.g., palindromes) can be also shown to be NL (e.g., by doing a dynamic algorithm simultaneously from the beginning and from the end). Is there a context-free language whose $L$-interleaving problem is NP-hard?