¿Qué tan rápido podemos decidir si un DFA dado es mínimo?

Minimizar los autómatas finitos deterministas (DFA) es un problema que se ha estudiado a fondo en la literatura, y se han propuesto varios algoritmos para resolver el siguiente problema: Dado un DFA , calcule un DFA mínimo correspondiente que acepte el mismo lenguaje que . La mayoría de estos algoritmos se ejecutan en tiempo polinómico.$\mathscr{A}$$\mathscr{A}$

Sin embargo, me pregunto si la variante de decisión de este problema: "dado un DFA , ¿es mínimo?" - se puede resolver de manera más eficiente que computar realmente el autómata mínimo. Obviamente, esto también se puede hacer de manera eficiente ejecutando, por ejemplo, el algoritmo de refinamiento de partición de Hopcroft y luego decidiendo si todas las particiones contienen exactamente un estado.$\mathscr{A}$$\mathscr{A}$

Como Yuval Filmus sugiere en su respuesta , la variante de capacidad de decisión se puede resolver más rápido, posiblemente utilizando los algoritmos estándar. Desafortunadamente, no puedo ver cómo (espero no perderme un punto obvio aquí).

Yuval señala en los comentarios aquí que los algoritmos más conocidos (como el anterior) se ejecutan en tiempo para alfabetos de tamaño constante. Por lo tanto, no solo estoy interesado en ganancias asintóticamente significativas en tiempo de ejecución, ya que estas parecen bastante improbables. Lo que más me molesta es que no puedo imaginar ningún "atajo" que pueda derivarse del hecho de que solo estamos interesados ​​en un sí-no-respuesta, ni siquiera un atajo que permita ahorrar una cantidad de tiempo asintóticamente insignificante. Creo que cada algoritmo sensible que decida la minimidad de un DFA tendría que minimizarlo y ver si algo cambia durante el proceso.$\mathcal{O}(n \log n)$

Es posible que este no sea exactamente el tipo de respuesta que está buscando, pero dado que preguntó sobre problemas de decisión, pensé que podría estar interesado en la complejidad del problema. Es -completo.$\mathsf{NL}$

Ahora, ¿qué significa que un DFA sea mínimo? Hay dos propiedades:

1. Cada estado es accesible: modo que podamos alcanzar desde el estado inicial siguiendo ; en símbolos: . q s w s → w$\forall q \in Q \; \exists w \in \Sigma^*$$q$$s$$w$$s \rightarrow_w q$

2. Cada par de estados se puede distinguir: con tal que e y (solo uno de es un estado de aceptación).q ≠ r ∃ w ∈ Σ ∗ q → w s r → w t | { s , t } ∩ F | = 1 s , $\forall q,r \in Q$$q \neq r$ $\exists w \in \Sigma^*$$q \rightarrow_w s$$r \rightarrow_w t$$|\{s,t\} \cap F| = 1$$s,t$

Tenga en cuenta que se puede calcular en el espacio logarítmico (es decir, ; solo siga su posición actual a medida que sigue letra por letra). Además, solo existe un número finito de alternancias entre y por lo que, como consecuencia del teorema Immerman-Szelepcsenyi , tenemos que el problema está en .L w ∀ ∃ N $x \rightarrow_w y$$\mathsf{L}$$w$$\forall$$\exists$$\mathsf{NL}$

La forma más fácil de ver que es difícil para es darse cuenta de que la propiedad 1 soluciona - inaccesibilidad, que es el problema difícil prototípico dirigido. Pero incluso si considera solo los DFA accesibles, el problema sigue siendo difícil (es decir, la propiedad 2 es -hard) y puede encontrar una prueba relativamente sencilla en el Lema 2.2 de Cho y Huynh (1992) . s t N $\mathsf{NL}$$s$$t$$\mathsf{NL}$

Por supuesto, utilicé el no determinismo, por lo que es un poco tosco en la forma en que difiere del algoritmo de Hopcroft. Pero sabemos que , por lo que puede usar esas construcciones para obtener un algoritmo más eficiente en espacio que Hopcroft (que por su propia naturaleza tiene que realizar un seguimiento de muchas particiones )$\mathsf{NL} \subseteq \mathsf{L}^2$$n$