THE LOGIC OF AUTOMATA

Publisher Website
Google Scholar
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 roles of topological models of automata, and the symmetry between inputs and outputs in hyperstate/hyperinput-determined systems are also discussed.

This publication has 32 references indexed in Scilit: