Quadratic automata

摘要

In this paper the notion of a quadratic automaton transformation is defined and studied. The automata considered transform infinite input sequences of elements from a finite commutative ring with identity to infinite output sequences. Results extending the linear automaton transformation theory of A. Nerode are derived and two distinct approaches to machine realization arise depending upon whether 2 is invertible in the base ring or not. Such a naturally occurring quadratic map as the AND function of elementary switching theory is easily realized in this setting.