O custo de uma consulta de equivalência para o DFA

12

Inspirado por esta pergunta , estou curioso sobre o seguinte:

Qual é a pior complexidade possível de verificar se um determinado DFA aceita o mesmo idioma que uma determinada expressão regular?

Isso é conhecido? A esperança seria que esse problema estivesse em P - que houvesse um polinômio de algoritmo no tamanho de ambos.

Lev Reyzin
fonte

Respostas:

16

De acordo com Garey e Johnson (p. 174), a EXPRESSÃO REGULAR NÃO UNIVERSALIDADE é completa no PSPACE. Este é o problema de decidir se uma expressão regular sobre se não gerar todas as cadeias. Portanto, seu problema também está completo no PSPACE.{0,1}

ArBrCBCCDACL(A)=L(r)D2poly(n)L(D)=NSPACE(poly(n))=NPSPACE=PSPACE, a última igualdade devido ao teorema de Savitch.

Yuval Filmus
fonte
Tem certeza de que está no PSPACE (caso contrário, seria apenas PSPACE-HARD)? Ou talvez seja suficiente verificar todas as seqüências de algum comprimento polinomial para ver se o regexp e o DFA concordam com todas elas? Isso é óbvio? :-)
Neal Young
4
Lembre-se de que a acessibilidade está em NL, portanto, embora o DFA correspondente à expressão regular seja exponencial, já que o acesso ao Oracle é barato, podemos descobrir se a diferença simétrica está vazia ou não em NPSPACE = PSPACE.
Yuval Filmus
Não vejo o resultado da dureza. Ou seja, como você reduz o problema acima à universalidade de expressões regulares?
Markus
2
Escolha o DFA que aceita tudo. Para mostrar dureza, reduza a NÃO UNIVERSALIDADE DE EXPRESSÃO REGULAR ao problema em questão.
Yuval Filmus
1
@YuvalFilmus Obrigado pela referência! Você provavelmente deve adicionar seu primeiro comentário à sua resposta, para completar, nos dois significados da palavra :)
Lev Reyzin