Complexidade parametrizada da inclusão de idiomas regulares

11

Estou interessado no problema clássico INCLUSÃO LÍNGUA REGULAR. Dada uma expressão regular , denotamos por L ( E ) a linguagem regular a ela associada. (As expressões regulares estão em um alfabeto fixo Σ , com a união de operações, estrela Kleene e concatenação.)EL(E)Σ

Entrada: Duas expressões regulares e E 2 Pergunta: É verdade que L ( E 1 ) L ( E 2 ) ?E1E2
L(E1)L(E2)

A INCLUSÃO REGULAR DA LÍNGUA é conhecida por ser completa no PSPACE [1].

O modo clássico de resolvê-lo (em PSPACE) é construir a AFNs e A 2 associada a E 1 e E 2 , para construir um DFA D 2 a partir de uma 2 , complementam-lo em um DFA D C 2 , e finalmente, construa o autômato de interseção A P a partir de A 1 e D C 2 correspondente à interseção de L ( E 1 ) e L ( E 2 ) CA1A2E1E2D2A2D2CAPA1D2CL(E1)L(E2)C. Agora se e só se existe um caminho não aceitar em uma P .L(E1)L(E2)AP

Se não me engano, todo o processo pode ser feito em tempo polinomial quando é uma linguagem fixa, uma vez que o blow-up única exponencial vem transformando Um 2 em D 2 . Melhor ainda, o problema é o FPT quando parametrizado por | E 2 | , o comprimento de E 2 .E2A2D2|E2|E2

Isso motiva minha pergunta:

Pergunta: Quando é uma expressão fixa, qual é a complexidade da INCLUSÃO REGULAR DA LINGUAGEM? Ele permanece completo no PSPACE?E1

[1] LJ Stockmeyer e AR Meyer. Problemas de palavras que requerem tempo exponencial: relatório preliminar. Anais do quinto Simpósio anual da ACM sobre Teoria da Computação, STOC '73, pp. 1-9.

Observação: como não especialista no campo, acho [1] (e artigos relacionados da época) bastante ilegíveis e não consegui encontrar outra prova da integridade do PSPACE - qualquer ponteiro para uma prova moderna, como em um livro, é muito bem vindo! Além disso, os autores parecem permitir quadratura em suas expressões regulares, o que hoje é bastante fora do padrão, acredito.)

Florent Foucaud
fonte
4
Ele permanece completo no PSPACE, pois a universalidade da linguagem (ou seja, E1 = Sigma *) está completa no PSPACE.
Denis
3
Btw permitir quadrado torna o problema EXPSPACE completo, os resultados que você mencionou são sem quadrado.
Denis
1
Para , é solucionável em tempo constante. Para E 1 = w para uma cadeia fixa w , é solucionável em tempo polinomial. Para E 1 = Σ * é PSPACE-completo. Será que não existe um de E 1 de tal modo que o problema é N P -completo? E1=E1=wwE1=ΣE1NP
Michael Wehar
2
OK, obrigado! @ Denis, por favor, transforme-a em uma resposta (com uma referência), e eu aceito!
Florent Foucaud 23/02
3
@MichaelWehar: Alguns casos CONP-completo são provou aqui, ( doi.org/10.1137/080743457 ), mas eles não são para fixos línguas (mas por muito restritas aulas de línguas)
Florent Foucaud

Respostas:

14

O caso particular da universalidade da linguagem (todas as palavras são aceitas?) É PSPACE-complete para expressões regulares ou NFAs. Responde à sua pergunta: em geral, o problema permanece completo no PSPACE, mesmo para fixo , pois a universalidade da linguagem corresponde a E 1 = Σ .E1E1=Σ

É realmente difícil encontrar uma prova moderna de dureza PSPACE legível para a universalidade de expressões regulares, como agora é considerada folclore. Aqui está um esquema de prova rápida que permite reconstruir a prova:


Considere-se uma máquina de Turing no alfabeto Σ usando o espaço polinomial p ( n ) , e deixe w Σ * ser uma palavra de entrada para M . Construiremos uma expressão regular e que aceite todas as palavras se e somente se M não aceitar execução em w .MΣp(n)wΣMeMw

LM$C0$C1$$Cf$CiMp(n)C0wCfCiCi+1MLMM

eΣ=Σ{$}eLMLMee1+e2++ekei

e1=(Σ)$(Σ<p(n)+Σ>p(n))$(Σ)
Cip(n)CiCi+1CiCi+1t(Σ)p(n)tttM
L(e)(Σ) if and only if LM if and only if M accepts w
portanto, reduzimos (polinomialmente) um problema arbitrário do PSPACE à universalidade de uma expressão regular. Deixei de fora alguns detalhes, mas isso deve permitir que você construa uma prova completa.

E1

(Σ)p(n)p(n)p(n)

[1] Sobre equivalência, contenção e cobertura de problemas para as linguagens regulares e sem contexto Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Revista de Ciências da Computação e Sistemas. Volume 12, Edição 2, Abril de 1976, Páginas 222-268

[2] O problema de equivalência para expressões regulares com quadratura requer espaço exponencial . Meyer, AR e L. Stockmeyer. 13º Simpósio do IEEE sobre comutação e teoria de autômatos, outubro de 1972, pp.125-129.

Denis
fonte
Uau, muito obrigado por compartilhar as referências !! Isso é legal !! :)
Michael Wehar
2
Um colega meu me indicou a seguinte pesquisa que lida com esse tipo de problemas regulares de linguagem e autômatos e contém outras referências úteis: sciencedirect.com/science/article/pii/S0890540110001999
Florent Foucaud