THE LOGIC OF AUTOMATA

Abstract

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.