TRANSPARENT CATEGORIES AND CATEGORIES OF TRANSITION SYSTEMS
Abstract
Several recent results in automata theory give evidence of the importance of homomorphisms in the study of transition systems and automata. It is natural therefore to inquire how much information can be retrieved from the algebra of homomorphism compositions with respect to transition systems. The natural mathematical framework for the discussion of this problem is categorical algebra. A category AW of the transition systems with input W is defined; W is any arbitrary fixed monoid, and with arbitrary sets of states. In this paper it is shown that AW has a generator, MW (which is W operating on itself as a transition system) and that exists a functor naturally equivalent to the identity functor of AW. A general exposition of the nature of properties which are retrievable from the "morphism-behavior" in an arbitrary category is presented so that it provides a rigorous general basis for studying "retrievable" properties and categories in which every structural property of objects and morphisms is "retrievable." It is proved that for a very broad class of input monoids, which includes all the types of input-monoids encountered in automata theory, the categories AW are transparent. That is, anything which can be said about the structure of transition systems with input W, can be said by referring to their homomorphisms only.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1965
- Accession Number
- AD0466445
Entities
People
- Yehoshafat Give'on
Organizations
- University of Michigan