Isomorphism Groups of Automata

ABSTRACT

This paper persues a discussion of certain algebraic properties of automata and their relationship to the structure (i.e., properties of the next state function) of automata. The device which is used for this study is the association of a group with each automaton. We introduce functions on automata and study the group of an automaton, a representation for the group elements and the direct product of automata. Finally, for a certain class of automata a necessary and sufficient condition, in terms of the group of the automaton, is given for insuring that an automaton can be represented as a direct product.

REFERENCES

• 1: RXBIN, M. O., AND SCOTT, D. Finite automata and their decision problems. IBM J. Rvs. Dev. 3 (Apr. 1959), 114-125.
• 2: GINSBURG, S. Some remarks on abstract machines. Trans. Amer. Math. Soc. 96 (1960), 4OO-444.
• 3: MOORS, E. F. Gedanken-experiments on sequential machines. In Automata Studies, pp. 129-153, Princeton (1956).
• 4: WEEG, G.P. Some group theoretic properties of strongly connected automata. Unpublished research at the Computer Laboratory, Michigan State University; May 1961.
• 5: G. P. Weeg, The Structure of an Automaton and Its Operation-Preserving Transformation Group, Journal of the ACM (JACM), v.9 n.3, p.345-349, July 1962 [doi>10.1145/321127.321131]
• 6: ZASSENrIAvS, H. The Theory of Groups. Chelsea Publishing Co., New York, N. Y., 1949.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

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

General Terms:
Theory