THE LOGIC OF AUTOMATA

Automata are the prime example of general systems over discrete spaces, and yet the theory of automata is fragmentary and it is not clear what makes a general structure an automaton. This paper investigates the logical foundations of automata relating it to the semantics of our notions of uncertainty, state and state-determined. A single framework is established for the conventional spectrum of automata: deterministic, probabilistic, fuzzy, and non-deterministic, which shows this set to be, in some sense, complete. Counter-examples are then developed to show that this spectrum alone is inadequate to describe the behaviour of certain forms of uncertain system. Finally a general formulation is developed based on the fundamental semantics of our notion of a state that shows that the logical Structure of an automaton must be at least a positive ordered semiring. The role of probability logic, its relationship to fuzzy logic, the rotes of topological models of automata, and the symmetry between inputs and outputs in hyperstate/hyperinput-determinedsystems are also discussed.