ON SOME CATEGORICAL ALGEBRA ASPECTS OF AUTOMATA THEORY: THE CATEGORICAL PROPERTIES OF TRANSITION SYSTEMS.
Abstract
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 referring 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. Categorical 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 if it does not depend on the particular labeling of the input alphabet. This study of the categorical properties of automata has two additional outcomes. First, we realize that categorical algebra methods can be applied to automata 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 automata, in particular, in getting a better understanding of the mathematical ideas employed in automata theory. In 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1966
- Accession Number
- AD0630257
Entities
People
- Yehoshafat Give'on
Organizations
- University of Michigan