Speaker: Bas Ploeger (OAS, TU/e)
Title: From NFA to minimal DFA

Abstract:
A common way of generating the minimal deterministic finite
automaton (DFA) out of a given nondeterministic one (NFA) is by
first applying the subset construction algorithm and then
minimizing the resulting DFA using (e.g.) minimization modulo
bisimulation equivalence. In the worst case the minimal DFA is
exponentially larger than the NFA; this bound cannot be improved.
However, in cases where the DFA generated by subset construction
is much larger than the minimal DFA, one starts wondering whether
the generation of lots of these "useless" states can be prevented.

In this talk I propose two algorithms which directly generate the
minimal DFA out of an NFA and prevent the generation of such
states. The complexity of these algorithms is higher than the
EXPTIME of subset construction. In practice, they can be modified
slightly to obtain versions that have the same complexity as
subset construction but will generate a smaller (though not
minimal) DFA in many cases.

Some preliminary results show that these algorithms are slower
than subset construction but use far less memory, which was our
main goal. Also, the resulting DFA is much smaller than the one
generated by subset construction. Therefore, we expect our
algorithms to allow for the generation of a DFA from an NFA in
cases where an implementation of traditional subset construction
runs out of memory.