Motivated by recent applications of finite automata to theoretical physics,
we study the minimization problem for nondeterministic automata (with outp
uts, but no initial states). We use Ehrenfeucht-Fraisse-like games to model
automata responses and simulations. The minimal automaton is constructed a
nd, in contrast with the classical case, proved to be unique up to an isomo
rphism. Finally, we investigate the partial ordering induced by automata si
mulations. For example, we prove that, with respect to this ordering, the c
lass of deterministic automata forms an ideal in the class of all automata.
(C) 2000-Elsevier Science B.V. All rights reserved.