Accession Number : AD0466445


Title :   TRANSPARENT CATEGORIES AND CATEGORIES OF TRANSITION SYSTEMS


Descriptive Note : Technical rept.


Corporate Author : MICHIGAN UNIV ANN ARBOR LOGIC OF COMPUTERS GROUP


Personal Author(s) : Give'on, Yehoshafat


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/466445.pdf


Report Date : May 1965


Pagination or Media Count : 42


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.


Descriptors :   *AUTOMATA , THEORY , COMPUTER LOGIC , MAPPING , OPERATORS(MATHEMATICS) , ALGEBRAIC TOPOLOGY , SET THEORY , MONOIDS


Subject Categories : Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE