Complexity of checking if two words have an interleaving in a language 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?
For a word $w=w_1\ldots w_{\ell}$ and for two integers $i,j$ with $1\le i\le j\le \ell$ we denote by $w(i,j)$ the subword $w_iw_{i+1}\ldots w_j$ of $w$.
Furthermore we let $w(0,0)$ denote the empty word.


Let $u=u_1\ldots u_m$ and $v=v_1\ldots v_n$ be the two words under consideration.
Assume that the context-free language $L$ is specified by a context-free grammar in Chomsky normal form.


Construct a dynamic program, where a state $[i,j,r,s,A]$ is specified by


two integers $i,j$ with $1\le i\le j\le m$ or $i=j=0$
two integers $r,s$ with $1\le r\le s\le n$ or $r=s=0$
a non-terminal symbol $A$ in the context-free grammar


For every state, decide whether in the context-free grammar there exists some derivation that starts with the non-terminal $A$ and that ends with some interleaving of the two words $u(i,j)$ and $w(r,s)$.
This decision can easily be made, if the states are handled in the right order (short subwords before longer subwords). 

All in all, this yields a polynomial time algorithm for the $L$-interleaving problem of any context-free language $L$.