We study several properties on finite deterministic incomplete automata without initial states. First we define several ways in which an incomplete automaton simulates another automaton. Further on we construct an incomplete automaton which simulates a given automaton S and has the minimum number of states compared to any other automaton simulating S. Finally, we study two computational complementarity principles for incomplete automata. In contrast with the case of complete automata, it is possible to construct incomplete three-state automata displaying both types of computational complementarity.
展开▼
