11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hopcroft's algorithm already runs in quasilinear time, so there isn't that much room for improvement. $\endgroup$ – Yuval Filmus Mar 2 '14 at 18:16
  • $\begingroup$ Yes, I edited my question so that it reflects this fact, @YuvalFilmus $\endgroup$ – Cornelius Brand Mar 2 '14 at 18:52
  • 1
    $\begingroup$ I believe the fastest known DFA minimization algorithm is still this one. It's faster than any algorithm published before 2008 running in $O(n+m \log n)$ time, where $m$ is the number of transitions. $\endgroup$ – Juho Mar 2 '14 at 19:42
  • $\begingroup$ seems unlikely to me the decision problem is equivalent in complexity to the minimization problem, the former seems possibly harder because it involves testing for DFA equivalence which is not nontrivial. so it seems the complexity of the decision problem is the maximum of "minimization or equivalence testing". and what is the complexity of equivalence testing? $\endgroup$ – vzn Mar 3 '14 at 1:17
  • $\begingroup$ @vzn Assuming you meant "[...] which is nontrivial": It does not necessarily have to, as e.g. the procedure I gave in my question avoids testing for equivalence. However, I also think that the problem is not easier than minimizing. $\endgroup$ – Cornelius Brand Mar 3 '14 at 5:30
5
$\begingroup$

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:

  1. 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$.

  2. 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).

$\endgroup$
  • $\begingroup$ this seems to improve space but not time complexity? $\endgroup$ – vzn Mar 3 '14 at 16:46
  • $\begingroup$ I agree with vzn. Although I like this answer, I am still interested in insights that are more closely related to the original question. $\endgroup$ – Cornelius Brand Mar 3 '14 at 16:57
  • $\begingroup$ @C.Brand My answer is meant to be tangential (hence the disclaimer at the start ;)) I just gave you the lowest complexity class for which I know the problem to be complete. There is a standard technique to convert $\mathsf{NL}$ algorithms into $\mathsf{P}$ ones (i.e. BFS on the configuration graph) but I don't think that construction will give you a faster time algorithm. $\endgroup$ – Artem Kaznatcheev Mar 3 '14 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.