Toward a Homological Algebra of Automata I: 1. The Representation and Completeness Theorem for Categories of Abstract Automata

摘要

In this paper the author formulates the categorical theory of abstract automata. Two immediate basic problems are posed. First, one wonders how restricted the study of abstract automata is when one confines himself to those properties which are formulated by means of the notions of category theory only. This is a mathematical question whose answer should be proved. The author proves the completeness of the categorical study of abstract automata for a wide class of input monoids, a class which includes all types of monoids employed in the theory of finite automata. In order to get this result, a general representation theorem for abstract automata is derived. The second question is psychological. How well does the categorical study of automata suit our intuitions and our problems. The answers to such a problem is not a matter of proof. The development presented in this paper has convinced the author of the potentiality of this new approach toward automata. Thus, this paper serves as a prelude to a series of papers which will exploit homological and categorical algebra methods for the sake of a mathematical theory of automata. (Author)