Technical Report ON SOME CATEGORICAL ALGEBRA ASPECTS OF AUTOMATA THEORY: THE CATEGORICAL PROPERTIES OF TRANSITION SYSTEMS

摘要

The ubiquity and usefulness of homomorphisms in various studies of automata lead us to consider the following problem. What can be said on automata by re¬ferring only to homomorphisms of automata? In the report we present a study of this problem with respect to a special type of automaton, namely with respect to transition systems.nCategorical algebra methods are applied to the precise formulation of this problem and to its solution. We find that if W is a monoid belonging to a broad class of monoids, then the categorical abstract properties of transition systems with input W are determined by the automorphisms of the monoid W. In particular, any property of automata without output is categorical iff it does not depend on the particular labeling of the input alphabet.nThis study of the categorical properties of automata has two additional out¬comes. First, we realize that categorical algebra methods can be applied to au¬tomata with arbitrary input monoids, with results pertinent to the theory of monoids. On the other hand it indicates a possible usefulness in the study of au¬tomata, in particular, in getting a better understanding of the mathematical ideas employed in automata theory.nIn order to support this point of view with respect to automata theory, we show that many actually studied properties of automata are categorical. And we give an example of a categorical examination and formulation of a particular study of perfect automata.