Finite nondeterministic automata: Simulation and minimality

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.