Note Concerning the Algebraic Theory of Automata
Harry E. Pickett · Journal of the ACM · 1967
If an automaton is strongly connected, all of its automorphisms are regular permutations. It is proved that given any two groups G and H of regular permutations on finite sets A and B , respectively, there exists strongly connected automata @@@@ and @@@@ such that G and H are the automorphisms groups of @@@@ and @@@@, @@@@ × @@@@ is strongly connected and the automorphism group of @@@@ × @@@@ is G × H . Also it is proved that the reduced semigroup of an automaton is a regular group of permutations iff the automorphism group of @@@@ is regular and @@@@ is strongly connected. Using this result we construct examples where the automorphism groups have the above property for all strongly connected automata on A and B , and other examples where the automorphism group of @@@@ × @@@@ properly contains G × H .