Die Kosten einer Äquivalenzabfrage für DFA

Inspiriert von dieser Frage bin ich neugierig auf Folgendes:

Wie komplex ist es im schlimmsten Fall, zu überprüfen, ob ein bestimmter DFA dieselbe Sprache wie ein bestimmter regulärer Ausdruck akzeptiert?

Ist das bekannt? Die Hoffnung wäre, dass dieses Problem in P liegt - dass es ein Algorithmuspolynom in der Größe von beiden gibt.

Laut Garey und Johnson (S. 174) ist die REGULARE EXPRESSION NON-UNIVERSALITY PSPACE-vollständig. Das ist das Problem der Entscheidung , ob ein regulärer Ausdruck über ist nicht alle Saiten erzeugen. Dein Problem ist also auch PSPACE-komplett.$\{0,1\}$

$A$$r$$B$$r$$C$$B$$C$$C$$D$$A$$C$$L(A) = L(r)$$D$$2^{\mathrm{poly}(n)}$$L(D) = \emptyset$$\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$, die letztere Gleichheit aufgrund des Satzes von Savitch.