Quelle est la complexité du problème de vide pour les DFA bidirectionnels?

Je me demande quelle est la complexité temporelle de la détermination du vide pour les DFA bidirectionnels? Autrement dit, des automates finis qui peuvent reculer sur leur bande d'entrée en lecture seule.

Selon Wikipedia, ils sont équivalents aux DFA, bien que les DFA équivalents puissent être exponentiellement plus importants. J'ai trouvé la complexité des états pour leurs compléments et leurs intersections, mais pas pour leurs tests de vide.

Est-ce que quelqu'un connaît un document où je pourrais le trouver?

Ami Google suggère ce qui suit: " L'exhaustivité PSPACE du problème de vide pour les automates à états finis déterministes bidirectionnels dans l'exercice 5.5.4 est due à Hunt (1973). " (An Introduction to the Theory of Computation, Eitan Gurari, Computer Science Press, 1989, en ligne )

Hunt, H. (1973). "Sur la complexité temporelle et magnétique des langues", Actes du 5e Symposium annuel de l'ACM sur la théorie de l'informatique, 10-19.

$\cal A$$\cal M$$x$$\cal A$$\cal M$$x$$x\$x_1\$\dots\$x_n$$x_i$$x$$\cal M$$\cal A$$x_i$$x_{i+1}$$|x|$$\cal A$

$\cal A$$\cal A$$x$$\cal A$$x$

La non-vacuité d'intersection pour les DFA est la suivante:

$D_1$$D_2$$D_k$

$w$$i \in [k]$$D_i$$w$

La non-vacuité d'intersection est un problème classique de PSPACE complet (Kozen 1977 - "Limites inférieures pour les systèmes de preuve naturelle")

Pertinence: Il y a une réduction paramétrée agréable et simple, de la non-vacance d'intersection pour les DFA à sens unique à la non-vacuité pour les DFA à deux voies.

Sélectionnez le nombre de DFA comme paramètre de non-vide d'intersection et le nombre de tours (passe de gauche à droite ou de droite à gauche) comme paramètre de non-vide pour DFA bidirectionnels.

$k$$(2k-2)$

$D_1$$D_2$$D_k$$(2k-2)$

$D_1$$D_2$$D_3$$D_k$

Si tous acceptent, alors il fait l'évaluation sur chacun d'eux et accepte ensuite. Si l'un d'entre eux rejette, il s'arrête (ne termine pas l'évaluation sur tous) et rejette immédiatement.

$k$$n^k$

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

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

Conclusion: Si vous deviez trouver un algorithme plus rapide de non-vide pour les DFA bidirectionnels, cela conduirait à une simulation plus efficace des machines non déterministes. Faites-moi savoir si vous avez des idées à partager. Merci d'avoir posé la question! :)