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

9

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

  • Entrada: duas palavrasvocê,vUMA
  • Saída: se existe uma intercalação de e , que está em .v Lvocêveu

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 vvocêvWvocêvWvocêvvocêv

Qual é a complexidade do problema INTERLEAVING, dependendo do idioma ? LeueuEm 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?eu
  • 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?Leueueu
a3nm
fonte

Respostas:

6

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 + 1w j de w . Além disso, deixamos w ( 0 , 0 ) denotar a palavra vazia.W=W1 1...WEu,j1 1EujW(Eu,j)WEuWEu+1 1...WjWW(0 0,0 0)

  • Vamos e v = v 1 ... v n ser as duas palavras em questão.você=você1 1...vocêmv=v1 1...vn
  • Suponha que a linguagem livre de contexto seja especificada por uma gramática livre de contexto na forma normal de Chomsky.eu

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 = 0i,j1ijmi=j=0
  • dois inteiros com 1 r s n ou r = s = 0r,s1rsnr=s=0
  • um símbolo não terminal na gramática livre de contextoA

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).Au(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 .LL

Gamow
fonte
Obrigado! Na verdade, eu não havia notado que essa variante do en.wikipedia.org/wiki/CYK_algorithm funcionaria para mostrar que o problema está em P para linguagens sem contexto. Dito isto, não vemos como mostrar que o problema está em NL usando esse algoritmo: parece que precisamos fazer um número logarítmico de suposições (a altura da árvore), sendo cada suposição logarítmica (ou seja, posições no corda). Alguma idéia sobre isso?
a3nm
2
@ a3nm Se a palavra vazia pertence a uma CFL já é difícil.
395 Sylvain
@Sylvain: OK, é difícil, mas é uma função do CFL. :) Lembre-se de que no meu problema a linguagem (ou uma CFL para ele) é fixa e a entrada são apenas as duas strings, portanto, não acho que esse argumento se aplique.
A3nm4
2
@ a3nm desculpe, eu realmente tinha perdido o fato de que o idioma estava corrigido. Então, o candidato natural seria a dureza do LogCFL.
Sylvain
@Sylvain: Está certo, obrigado! Então, de fato, acho que o problema da palavra é difícil para o LogCFL, mesmo para uma linguagem CFL fixa (ou seja, a linguagem mais difícil de Greibach), então, em particular, existem linguagens CFL para as quais meu problema é difícil para o LogCFL (instale a segunda string vazia ) Por outro lado, imagino que o algoritmo de Gamow esteja no LogCFL (?). Ainda assim, isso me faz pensar sobre os idiomas para os quais o meu problema seria mais fácil que este limite, e como eles poderiam ser categorizados ...
a3nm