patternMinor
How fast can we decide whether a given DFA is minimal?
Viewed 0 times
fastcandfadecidehowminimalwhethergiven
Problem
Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem:
Given a DFA $\mathscr{A}$, compute a corresponding minimal DFA accepting the same language as $\mathscr{A}$.
Most of these algorithms run in polynomial time.
However, I wonder whether the decision variant of this problem - "given a DFA $\mathscr{A}$, is $\mathscr{A}$ minimal?" - can be solved more efficiently than actually computing the minimal automaton.
Obviously, this can also be done efficiently by running for example Hopcroft's partition-refinement algorithm and then deciding whether all partitions contain precisely one state.
As Yuval Filmus suggests in his answer, the decidability variant can be solved faster, possibly by using the standard algorithms.
Unfortunately, I cannot see how (I hope I am not missing an obvious point here).
Yuval points out in the comments here that the best known algorithms (like the one above) run in time $\mathcal{O}(n \log n)$ for constant-sized alphabets. Therefore, I am not only interested in asymptotically significant gains in runtime, as these seem rather unlikely. What bothers me most is that I cannot imagine any "shortcut" that might be drawn from the fact that we are only interested in a yes-no-answer - not even a shortcut that allows for saving an asymptotically negligible amount of time. I feel that every sensible algorithm that decides the minimality of a DFA would have to actually minimize the DFA and see if anything changes during the process.
Given a DFA $\mathscr{A}$, compute a corresponding minimal DFA accepting the same language as $\mathscr{A}$.
Most of these algorithms run in polynomial time.
However, I wonder whether the decision variant of this problem - "given a DFA $\mathscr{A}$, is $\mathscr{A}$ minimal?" - can be solved more efficiently than actually computing the minimal automaton.
Obviously, this can also be done efficiently by running for example Hopcroft's partition-refinement algorithm and then deciding whether all partitions contain precisely one state.
As Yuval Filmus suggests in his answer, the decidability variant can be solved faster, possibly by using the standard algorithms.
Unfortunately, I cannot see how (I hope I am not missing an obvious point here).
Yuval points out in the comments here that the best known algorithms (like the one above) run in time $\mathcal{O}(n \log n)$ for constant-sized alphabets. Therefore, I am not only interested in asymptotically significant gains in runtime, as these seem rather unlikely. What bothers me most is that I cannot imagine any "shortcut" that might be drawn from the fact that we are only interested in a yes-no-answer - not even a shortcut that allows for saving an asymptotically negligible amount of time. I feel that every sensible algorithm that decides the minimality of a DFA would have to actually minimize the DFA and see if anything changes during the process.
Solution
This might not be exactly the sort of answer you are looking for, but since you asked about decision problems, I thought you might be interested in the complexity of the problem. It is $\mathsf{NL}$-complete.
Now, what does it mean for a DFA to be minimal? There are two properties:
-
Every state is reachable: $\forall q \in Q \; \exists w \in \Sigma^*$ such that we can reach $q$ from the start state $s$ by following $w$; in symbols: $s \rightarrow_w q$.
-
Every pair of states is distinguishable: $\forall q,r \in Q$ with $q \neq r$ $\exists w \in \Sigma^*$ such that $q \rightarrow_w s$ and $r \rightarrow_w t$ and $|\{s,t\} \cap F| = 1$ (only one of $s,t$ is an accept state).
Notice that the $x \rightarrow_w y$ can be computed in log-space (i.e. $\mathsf{L}$; just track your current position as you follow $w$ one letter at a time). Further, there is only a finite number of alternations between $\forall$ and $\exists$ so as a consequence of the Immerman-Szelepcsenyi theorem, we have that the problem is in $\mathsf{NL}$.
The easiest way to see that it is hard for $\mathsf{NL}$ is to notice that property 1 solves $s$-$t$ directed unreachability, which is the prototypical hard problem. But even if you consider only reachable DFAs, the problem is still hard (i.e. property 2 is $\mathsf{NL}$-hard) and you can find a relatively straightforward proof in Lemma 2.2 of Cho & Huynh (1992).
Of course, I used non-determinism, so it is a bit of a cough-out in the way it differs from Hopcroft's algorithm. But we know that $\mathsf{NL} \subseteq \mathsf{L}^2$, so you can use those constructions to get yourself a more space-efficient algorithm than Hopcroft (which by its very nature has to keep track of $n$ many partitions).
Now, what does it mean for a DFA to be minimal? There are two properties:
-
Every state is reachable: $\forall q \in Q \; \exists w \in \Sigma^*$ such that we can reach $q$ from the start state $s$ by following $w$; in symbols: $s \rightarrow_w q$.
-
Every pair of states is distinguishable: $\forall q,r \in Q$ with $q \neq r$ $\exists w \in \Sigma^*$ such that $q \rightarrow_w s$ and $r \rightarrow_w t$ and $|\{s,t\} \cap F| = 1$ (only one of $s,t$ is an accept state).
Notice that the $x \rightarrow_w y$ can be computed in log-space (i.e. $\mathsf{L}$; just track your current position as you follow $w$ one letter at a time). Further, there is only a finite number of alternations between $\forall$ and $\exists$ so as a consequence of the Immerman-Szelepcsenyi theorem, we have that the problem is in $\mathsf{NL}$.
The easiest way to see that it is hard for $\mathsf{NL}$ is to notice that property 1 solves $s$-$t$ directed unreachability, which is the prototypical hard problem. But even if you consider only reachable DFAs, the problem is still hard (i.e. property 2 is $\mathsf{NL}$-hard) and you can find a relatively straightforward proof in Lemma 2.2 of Cho & Huynh (1992).
Of course, I used non-determinism, so it is a bit of a cough-out in the way it differs from Hopcroft's algorithm. But we know that $\mathsf{NL} \subseteq \mathsf{L}^2$, so you can use those constructions to get yourself a more space-efficient algorithm than Hopcroft (which by its very nature has to keep track of $n$ many partitions).
Context
StackExchange Computer Science Q#22191, answer score: 6
Revisions (0)
No revisions yet.