Complexidade de verificar se duas palavras têm uma intercalação em um idioma

Para um idioma fixo em algum alfabeto , vamos considerar o seguinte problema, que chamo de INTERLEAVING :A L$L$$A$$L$

• Entrada: duas palavras$u, v \in A^*$
• Saída: se existe uma intercalação de e , que está em .v $u$$v$$L$

Aqui, uma intercalação de duas palavras e é uma palavra que pode ser obtida intuitivamente pegando as letras de e , mantendo sua ordem relativa. Formalmente, é uma intercalação de e se pudermos particioná-lo em duas subsequências separadas, uma que é igual a e a outra que é igual a . Por exemplo, "bheleloll" é uma intercalação de "olá" e "sino".v w u v w u v u $u$$v$$w$$u$$v$$w$$u$$v$$u$$v$

Qual é a complexidade do problema INTERLEAVING, dependendo do idioma ? $L$$L$Em particular:

• Se for regular, podemos resolver o problema com um algoritmo dinâmico nas duas strings que mostra que ele está na classe NL. É NL-difícil para alguns idiomas regulares? No entanto, para alguns idiomas regulares, o problema está claramente em L (espaço de registro determinístico). Existe alguma caracterização dos idiomas para os quais o problema está em L?$L$
• Se não for regular, o problema ainda estará em NL quando tiver complexidade de espaço determinístico on-line polinomial (veja aqui esta noção ou minha pergunta anterior ). No entanto, isso não abrange, por exemplo, todas as linguagens sem contexto; no entanto, alguns outros (por exemplo, palíndromos) também podem ser mostrados como NL (por exemplo, executando um algoritmo dinâmico simultaneamente desde o início e até o fim). Existe uma linguagem livre de contexto cujo problema de intercalação em é NP-difícil?$L$$L$$L$

Para uma palavra e para dois números inteiros i , j com 1 ≤ i ≤ j ≤ ℓ , denotamos por w ( i , j ) a subpalavra w i w i + 1 … w j de w . Além disso, deixamos w ( 0 , 0 ) denotar a palavra vazia.$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)$

• Vamos e v = v 1 ... v n ser as duas palavras em questão.$u=u_1\ldots u_m$$v=v_1\ldots v_n$
• Suponha que a linguagem livre de contexto seja especificada por uma gramática livre de contexto na forma normal de Chomsky.$L$

Construa um programa dinâmico, em que um estado seja especificado por$[i,j,r,s,A]$

• dois inteiros com 1 ≤ i ≤ j ≤ m ou i = j = $i,j$$1\le i\le j\le m$$i=j=0$
• dois inteiros com 1 ≤ r ≤ s ≤ n ou r = s = $r,s$$1\le r\le s\le n$$r=s=0$
• um símbolo não terminal na gramática livre de contexto$A$

Para cada estado, decidir se na gramática livre de contexto existe alguma derivação que começa com o não-terminal de e que termina com algum entrelaçamento das duas palavras u ( i , j ) e W ( r , s ) . Essa decisão pode ser facilmente tomada se os estados forem tratados na ordem correta (subpalavras curtas antes de subpalavras mais longas).$A$$u(i,j)$$w(r,s)$

Em suma , isso gera um algoritmo de tempo polinomial para o problema de intercalação em de qualquer linguagem L sem contexto .$L$$L$