Complejidad de verificar si dos palabras tienen un intercalado en un idioma

Para un lenguaje fijo en algún alfabeto , consideremos el siguiente problema, que llamo -INTERLEAVING :A L$L$$A$$L$

• Entrada: dos palabras $u, v \in A^*$
• Salida: si existe un entrelazado de $u$ y $v$ que está en $L$ .

Aquí, un entrelazado de dos palabras $u$ y $v$ es una palabra $w$ que puede obtenerse intuitivamente tomando las letras de $u$ y $v$ manteniendo su orden relativo. Formalmente, $w$ es un entrelazado de $u$ y $v$ si podemos dividirlo en dos subsecuencias disjuntas, una que es igual a $u$ y la otra que es igual a $v$ . Por ejemplo, "bheleloll" es una combinación de "hola" y "campana".

¿Cuál es la complejidad del problema $L$ -INTERLEAVING, dependiendo del lenguaje $L$ ? En particular:

• Si $L$ es regular, entonces podemos resolver el problema con un algoritmo dinámico en las dos cadenas que muestra que está en la clase NL. ¿Es difícil para algunos idiomas regulares? Sin embargo, para algunos lenguajes regulares, el problema está claramente en L (espacio de registro determinista). ¿Existe alguna caracterización de los idiomas para los cuales el problema está en L?
• Si $L$ no es regular, el problema todavía está en NL cuando $L$ tiene una complejidad de espacio determinista polinómica en línea (vea aquí esta noción o mi pregunta anterior ). Sin embargo, esto no cubre, por ejemplo, todos los lenguajes libres de contexto; sin embargo, también se puede demostrar que algunos otros (por ejemplo, palíndromos) son NL (por ejemplo, al hacer un algoritmo dinámico simultáneamente desde el principio y desde el final). ¿Existe un lenguaje sin contexto cuyo problema de intercalación en $L$ es NP-hard?

Para una palabra y para dos enteros con denotamos con la subparte de . Además, dejamos que denote la palabra vacía. i , j 1 ≤ i ≤ j ≤ ℓ w ( i , j ) w i w i + 1 ... w j w w ( 0 , 0 $w=w_1\ldots w_{\ell}$$i,j$$1\le i\le j\le \ell$$w(i,j)$$w_iw_{i+1}\ldots w_j$$w$$w(0,0)$

• Sean y las dos palabras bajo consideración. v = v 1 ... v $u=u_1\ldots u_m$$v=v_1\ldots v_n$
• Suponga que el lenguaje libre de contexto está especificado por una gramática libre de contexto en forma normal de Chomsky.$L$

Construya un programa dinámico, donde un estado se especifica mediante$[i,j,r,s,A]$

• dos enteros con o1 ≤ i ≤ j ≤ m i = j = $i,j$$1\le i\le j\le m$$i=j=0$
• dos enteros con or1 ≤ r ≤ s ≤ n r = s = $r,s$$1\le r\le s\le n$$r=s=0$
• un símbolo no terminal en la gramática libre de contexto$A$

Para cada estado, decidir si en la gramática libre de contexto existe alguna derivación que comienza con el no terminal y que termina con un poco de entrelazado de las dos palabras y . Esta decisión se puede tomar fácilmente si los estados se manejan en el orden correcto (subpalabras cortas antes que subpalabras más largas).u ( i , j ) w ( r , s $A$$u(i,j)$$w(r,s)$

Con todo, esto produce un algoritmo de tiempo polinómico para el problema de intercalación de cualquier lenguaje sin contexto .$L$$L$