Canonical Minimal Nondeterministic Automata accepting Regular Languages.
Speaker: Robert Myers
Joint work with: Jiri Adamek, Stefan Milius and Henning Urbat.
Abstract: For any regular language L there is a unique finite nondeterministic automaton accepting L which is minimal amongst all nondeterministic acceptors, relative to a certain measure. It is never larger than the minimal deterministic automaton and can be exponentially smaller. Although it already exists in the literature, the characterisation amongst all acceptors seems to be new, as is the Brzozowski-style minimization algorithm one can use to compute it.
This result sits within a coalgebraic framework which unifies various canonical nondeterministic acceptors of regular languages. The basic idea is to compute the minimal deterministic automaton in a locally finite variety and then reinterpret it as a smaller nondeterministic automaton, relative to the carrier algebra’s generators.