TRANSPARENT CATEGORIES AND CATEGORIES OF TRANSITION SYSTEMS
MICHIGAN UNIV ANN ARBOR LOGIC OF COMPUTERS GROUP
Pagination or Media Count:
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.
- Operations Research