ON ENDOMORPHISMS AND CONGRUENCES OF AUTOMATA,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1967
- Accession Number
- AD0647157
Entities
People
- Rudolf Bayer
Organizations
- Boeing