10

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?
Community
  • 1
a3nm
  • 9,269
  • 27
  • 86

1 Answers1

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

Gamow
  • 5,772
  • 6
  • 25
  • 39
  • 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? – a3nm Apr 03 '17 at 16:54
  • 2
    @a3nm Whether the empty word belongs to a CFL is already P-hard. – Sylvain Apr 04 '17 at 11:09
  • @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. – a3nm Apr 04 '17 at 13:23
  • 2
    @a3nm sorry I had indeed missed the fact that the language was fixed. Then the natural candidate would be LogCFL-hardness. – Sylvain Apr 05 '17 at 08:46
  • @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... – a3nm Apr 06 '17 at 09:52