Accession Number : AD0666457

Title :   ALGEBRA AUTOMATA II: THE CATEGORICAL FRAMEWORK FOR DYNAMIC ANALYSIS.

Descriptive Note : Interim rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF ELECTRICAL ENGINEERING

Personal Author(s) : Give'on,Y. ; Arbib,M. A.

Report Date : 1967

Pagination or Media Count : 40

Abstract : The treatment of algebra automata is extended to automata employing algebras over arbitrary theories. To this end Eilenberg and Wright's approach to the notion of a theory and its algebras originated by Lawvere are represented. Special attention is given here to the free theories which correspond, in ordinary automata theory, to the free monoids. For example, the free theories (like the free monoids) are characterized as the projective objects in the category of theories with surjective morphisms of theories only. For a theory T, a T-automation is defined in a straightforward analogy with the notion of an automation with an arbitrary input monoid. Our definition of a T-automation becomes obvious once it is recognized that a T-algebra is the appropriate explication for a right-action of T on a set. Consequently, the construction of a minimal realization and of a minimal dynamics of any given response function f on a theory is analogous to the same construction with respect to a mapping f on a monoid. Also the basic division lemmata which underlie Krohn and Rhodes' composition theory of machines are true for response function on free theories. (Author)

Descriptors :   (*ALGEBRA, AUTOMATA), SET THEORY, MAPPING(TRANSFORMATIONS), MONOIDS, RESPONSE, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE