Note Concerning the Algebraic Theory of Automata

ABSTRACT

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.

REFERENCES

• 1: ELGOT, C.C. Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98 (1961), 21-51.
• 2: A. C. Fleck, Isomorphism Groups of Automata, Journal of the ACM (JACM), v.9 n.4, p.469-476, Oct. 1962 [doi>10.1145/321138.321144]
• 3: MARICA. J. G., AND BRXA.NT, S .J . Unary algebras. Pacific J. Math. 10 (1960), 1347-1359.
• 4: G. P. Weeg, The Automorphism Group of the Direct Product of Strongly Related Automata, Journal of the ACM (JACM), v.12 n.2, p.187-195, April 1965 [doi>10.1145/321264.321269]
• 5: WIELANDT, H. Finite Permutation Groups. Academic Press, New York, 1964
• 6: BIRKHOFF, G. Lattice Theory (Rev. Ed.). Amer. Muth. Soc. Colloq. Publications, 1948, p. 96, Exercise 4.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Performance, Theory, Verification