Coût d'une requête d'équivalence pour DFA

Inspiré par cette question , je suis curieux de savoir ce qui suit:

Quelle est la pire des situations pour vérifier si un DFA donné accepte le même langage qu'une expression régulière donnée?

Est-ce connu? L'espoir serait que ce problème soit en P - qu'il existe un algorithme polynomial dans la taille des deux.

Selon Garey et Johnson (p. 174), la NON-UNIVERSALITÉ D'EXPRESSION RÉGULIÈRE est complète sur PSPACE. C'est le problème de décider si une expression régulière sur ne génère pas toutes les chaînes. Votre problème est donc également complet sur PSPACE.$\{0,1\}$

Voici une façon de voir que le problème de l'OP est dans PSPACE. Étant donné un DFA et une expression régulière , construisez un NFA pour et utilisez la construction de l'ensemble de puissance pour construire virtuellement un DFA équivalent à ; nous ne garderons pas en mémoire, mais nous avons un accès Oracle à utilisant uniquement l'espace polynomial. Construisez maintenant virtuellement un DFA pour la différence symétrique de et utilisant la construction du produit. Ce DFA n'accepte aucune chaîne (et donc$A$$r$$B$$r$$C$$B$$C$$C$$D$$A$$C$$L(A) = L(r)$) s'il n'y a pas de chemin entre l'état de départ et l'état d'acceptation. Puisque l'accessibilité est en NL et a une taille , nous pouvons vérifier si dans , cette dernière égalité due au théorème de Savitch.$D$$2^{\mathrm{poly}(n)}$$L(D) = \emptyset$$\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$