Accession Number : AD0647157

Title :   ON ENDOMORPHISMS AND CONGRUENCES OF AUTOMATA,

Corporate Author : BOEING SCIENTIFIC RESEARCH LABS SEATTLE WASH MATHEMATICS RESEARCH LAB

Personal Author(s) : Bayer,Rudolf

Report Date : JAN 1967

Pagination or Media Count : 30

Abstract : The interconnections between automorphisms and congruences of automata have been considered. Attention was mainly focused on automata which are of particular interest for practical applications. From a mathematical point of view, however, the theory is heavily restricted in several ways: (1) Only the rather restricted class of strongly connected automata is investigated. (2) Attention is limited to congruences whose classes are the transitivity classes of groups of automorphisms. In the present paper all these restrictions are removed and the structure relations between the endomorphisms, automorphisms and all congruence relations of an arbitrary, not necessarily finite automaton are investigated. It is shown how the symmetries of an automaton carry over to symmetries of the lattice of congruence relations and to symmetries of quotient automata. Closure operations are defined on the sets of endomorphisms and congruence relations. It is shown that in both structures the closed sets form a complete lattice and that these lattices are dually isomorphic. Finally, it is indicated how this purely algebraic theory can be applied to the decomposition theory of automata in various ways. (Author)

Descriptors :   (*AUTOMATA, *MATHEMATICAL LOGIC), (*MAPPING(TRANSFORMATIONS), AUTOMATA), SET THEORY, ALGEBRA

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE