<p>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.</p>

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

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

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

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

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

CC BY-SA 3.0
2017-04-03T16:54:12.120Z
Thanks! Indeed I hadn't noticed that this variant of https://en.wikipedia.org/wiki/CYK_algorithm would work to show that the problem is in P for context-free languages. That said, we don't see how to show that the problem is in NL using this algorithm: we seem to need to make a logarithmic number of guesses (the height of the tree), each guess being logarithmic (i.e., positions in the string). Any ideas about this?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-04T11:09:03.763Z
@a3nm Whether the empty word belongs to a CFL is already P-hard.
Sylvain
CC BY-SA 3.0
2017-04-04T13:23:07.860Z
@Sylvain: OK it is P-hard, but as a function of the CFL. :) Remember that in my problem the language (or a CFL for it) are fixed, and the input is only the two strings, so I don't think that this argument applies.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-05T08:46:00.910Z
@a3nm sorry I had indeed missed the fact that the language was fixed.  Then the natural candidate would be LogCFL-hardness.
Sylvain
CC BY-SA 3.0
2017-04-06T09:52:38.227Z
@Sylvain: That's right, thanks! So indeed I guess that the word problem is LogCFL-hard even for a fixed CFL language (i.e., Greibach's hardest language), so in particular there are CFL languages for which my problem is LogCFL-hard (take instances where the second string is empty). Conversely I imagine that Gamow's algorithm is in LogCFL (?). Still, this makes me wonder about the languages for which my problem would be easier that this bound, and how they could be categorized...
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-03T16:09:04.020Z
2017-04-03T16:09:04.020Z
Gamow
<p>For a fixed language $L$ on some alphabet $A$, let us consider the following problem, that I call <em>$L$-INTERLEAVING</em>:</p>

<ul>
<li>Input: two words $u, v \in A^*$</li>
<li>Output: whether there exists an <em>interleaving</em> of $u$ and $v$ which is in $L$.</li>
</ul>

<p>Here, an <em>interleaving</em> 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".</p>

<p><strong>What is the complexity of the $L$-INTERLEAVING problem, depending on the language $L$?</strong> In particular:</p>

<ul>
<li>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. <strong>Is it NL-hard for some regular languages?</strong> However, for some regular languages, the problem is clearly in L (deterministic logspace). <strong>Is there some characterization of the languages for which the problem is in L?</strong></li>
<li>If $L$ is not regular, the problem is still in NL when $L$ has polynomial online deterministic space complexity (see <a href="https://www.cs.ox.ac.uk/blogs/nathanael-fijalkow/2015/11/17/online-space-complexity-a-few-results-and-many-questions/" rel="nofollow noreferrer">here</a> for this notion, or <a href="https://cstheory.stackexchange.com/questions/22424/languages-recognized-by-polynomial-size-dfas/22441">my earlier question</a>). 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). <strong>Is there a context-free language whose $L$-interleaving problem is NP-hard?</strong></li>
</ul>

<cc.complexity-theory><reference-request><regular-language>
Complexity of checking if two words have an interleaving in a language
Antoine Amarilli 'a3nm'
# Complexity of checking if two words have an interleaving in a language

(Asked by: username_0 on 2017-04-03)

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](https://www.cs.ox.ac.uk/blogs/nathanael-fijalkow/2015/11/17/online-space-complexity-a-few-results-and-many-questions/) for this notion, or [my earlier question](https://cstheory.stackexchange.com/questions/22424/languages-recognized-by-polynomial-size-dfas/22441)). 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?**

**Tags:** cc.complexity-theory, reference-request, regular-language


---

## 1 answers

### Answer by username_1 on 2017-04-03. Score: 7

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

> **Comments:**
> **username_0**: Thanks! Indeed I hadn't noticed that this variant of https://en.wikipedia.org/wiki/CYK_algorithm would work to show that the problem is in P for context-free languages. That said, we don't see how to show that the problem is in NL using this algorithm: we seem to need to make a logarithmic number of guesses (the height of the tree), each guess being logarithmic (i.e., positions in the string). Any ideas about this?  
> **username_2**: @a3nm Whether the empty word belongs to a CFL is already P-hard.  
> **username_0**: @username_2: OK it is P-hard, but as a function of the CFL. :) Remember that in my problem the language (or a CFL for it) are fixed, and the input is only the two strings, so I don't think that this argument applies.  
> **username_2**: @a3nm sorry I had indeed missed the fact that the language was fixed.  Then the natural candidate would be LogCFL-hardness.  
> **username_0**: @username_2: That's right, thanks! So indeed I guess that the word problem is LogCFL-hard even for a fixed CFL language (i.e., Greibach's hardest language), so in particular there are CFL languages for which my problem is LogCFL-hard (take instances where the second string is empty). Conversely I imagine that username_1's algorithm is in LogCFL (?). Still, this makes me wonder about the languages for which my problem would be easier that this bound, and how they could be categorized...  

---

