Abstract:
We study finite deterministic incomplete automata without initial states. This means that
at any stage of a computation there is at most one transition to the next state. We will first investigate how two incomplete automata can simulate each other. 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 Moore's
uncertainty 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
complementarity.
