Abstract:
Motivated by recent applications of finite automata to theoretical physics, we
study the minimization problem for nondeterministic automata (with outputs, but no
initial states). We use Ehrenfeucht-Fraïsse-like games to model automata responses
and simulations. The minimal automaton is constructed and, in contrast with the
classical case, proved to be unique up to an isomorphism. Finally, we investigate
the partial ordering induced by automata simulations. For example, we prove that,
with respect to this ordering, the class of deterministic automata forms an ideal in
the class of all automata.