On the Structures of an Automaton and Its Input Semigroup
Robert H. Oehmke · Journal of the ACM · 1963
In this paper, relationships are developed between the structure of an automaton A and the structure of its input semigroup S. For a particular class of automata called "cyclic" automata it is shown that each member of this class can be realized as an intrinsic structure on the semigroup S.With such relationships existing it seems possible that greater use can be made of the existing literature on the structures of semigroups in the algebraic theory of automata.In Section 1 preliminary definitions and results are stated, most of which are essentially contained in Rabin and Scott [3] and Clifford [1; Sections 1.4 and 1.5].They are included here for clarity of presentation.In Section 2 some of the relationships between the two systems are established.In Section 3 an ~pplication is made to the isomorphism group of A.