Qual é a complexidade do problema de vazio para DFAs bidirecionais?

Pergunto-me, qual é a complexidade de tempo para determinar o vazio para DFAs bidirecionais? Ou seja, autômatos finitos que podem retroceder na fita de entrada somente leitura.

Segundo a Wikipedia, eles são equivalentes aos DFAs, embora o DFA equivalente possa ser exponencialmente maior. Encontrei complexidade de estado para os complementos e interseções, mas não para o teste de vazio.

Alguém sabe de um trabalho onde eu poderia encontrar isso?

Amigo Google sugere o seguinte " A completude PSPACE do problema de vazio para autômatos de estado finito determinístico de mão dupla no Exercício 5.5.4 é devido a Hunt (1973). " (Introdução à Teoria da Computação, Eitan Gurari, Computador Science Press, 1989, online )

Hunt, H. (1973). "Sobre a complexidade do tempo e da fita das línguas", Anais do 5º Simpósio Anual da ACM sobre Teoria da Computação, 10-19.

( Agora observei a referência ) O artigo está escrito de maneira abstrata, como você observa. A parte crucial para nós é a prova de Thm 3.7, onde é sugerido que se possa construir um 2FSA que aceite cálculos válidos de um autômato limitado linear M em uma cadeia fixa (!) X (que é próxima da definição de PSPACE ) O 2FSA A é construtível em tempo polinomial (no tamanho de M e x ). Uma computação de um LBA pode ser escrita como x $ x 1 $ … $ x n em que x i são todos do mesmo comprimento que$\cal A$$\cal M$$x$$\cal A$$\cal M$$x$$x\$x_1\$\dots\$x_n$$x_i$ e são passos consecutivos de M . Como A verifica se x i e x i + 1 são iguais (até uma mudança muito local de um estado e um único símbolo como a operação de um LBA)? Verificando letra por letra, nos dois sentidos da fita. Para isso, precisamos de um contador de tamanho | x | implementado no controle estatal finita de A .$x$$\cal M$$\cal A$$x_i$$x_{i+1}$$|x|$$\cal A$

Acontece que o problema é mencionado no apêndice da referência clássica de Garey & Johnson, Computers and Intratability , problema [AL2] "Não-vazio bidirecional de autômatos de estado finito" com a observação explícita "PSPACE-complete, mesmo que é determinístico ". Faça referência novamente Hunt, com o esclarecimento "Transformação de aceitação linear de autômatos limitados" (dado LBA A e entrada x , A aceita x ?). O último problema é [AL3] com referência ao famoso artigo de Karp (1972) "Redutibilidade entre problemas combinatórios" (onde a aceitação do LBA é mencionada como reconhecimento sensível ao contexto).$\cal A$$\cal A$$x$$\cal A$$x$

O não vazio de interseção para os DFA é o seguinte:

Entrada: uma lista finita de , D 2 , ...,$D_1$$D_2$.$D_k$

Pergunta: Existe uma string tal que para cada i ∈ [ k ] , D i aceite$w$$i \in [k]$$D_i$ ? Em outras palavras, a interseção de seus idiomas regulares associados não está vazia?$w$

O não vazio de interseção é um problema clássico completo do PSPACE (Kozen 1977 - "Limites inferiores para sistemas de prova natural")

Relevância: há uma redução parametrizada agradável e simples de não-vazio de interseção para DFAs unidirecionais para não-vazio para DFAs bidirecionais.

Escolha o número de DFAs como o parâmetro para Não Vazio de Interseção e o número de voltas (alterna de mover para a esquerda para a direita ou da direita para a esquerda) como o parâmetro para Não Vazio para DFAs de duas vias.

Reivindicação: Não Vazio de Interseção para DFA é redutível a Não Vazio para ( 2 k - 2 $k$$(2k-2)$ DFAs bidirecionais de voltas. (Acredito que haja uma redução relacionada para a outra direção também.)

Dado , D 2 , ..., D k , podemos construir a ( 2 k - 2 $D_1$$D_2$$D_k$$(2k-2)$ Vire bidirecional DFA que avalia cada um dos DFA de por um string de entrada de cada vez.

Primeiro, ele avalia na entrada. Em seguida, move a cabeça da fita de volta ao início e avalia D 2 na entrada. Em seguida, ele move a cabeça da fita de volta ao início e avalia D 3 na entrada. ... Finalmente, move a cabeça da fita de volta ao início e avalia D $D_1$$D_2$$D_3$$D_k$ na entrada.

Se todos eles aceitarem, faz a avaliação em todos eles e depois aceita. Se um deles rejeitar, será interrompido (não concluirá a avaliação de todos) e imediatamente será rejeitado.

$k$$n^k$

Link relacionado: /cstheory/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time/29166#29166

$(2k-2)$$n^k$

Conclusão: Se você encontrasse um algoritmo mais rápido para não-vazio para DFAs bidirecionais, isso levaria a uma simulação mais eficiente de máquinas não determinísticas. Deixe-me saber se você tem alguma idéia para compartilhar. Obrigado por fazer a pergunta! :)