Group-Type Automata

ABSTRACT

The purpose is to investigate the input structure of automata which have a group-like character. The class of perfect automata investigated by Fleck in [2] and Weeg in [6] is a proper subclass of those considered here.

REFERENCES

• 1: EEarry, J. C. On some properties of the semigroup of a machine which are preserved under state minimization. IBM Iles. Pap. RCl199, May 1964.
• 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: HtLL, M., Jn. The Theory of Groups. The Macmillan Company, New York, 1959.
• 4: Robert H. Oehmke, On the Structures of an Automaton and Its Input Semigroup, Journal of the ACM (JACM), v.10 n.4, p.521-525, Oct. 1963 [doi>10.1145/321186.321194]
• 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: -- The group and semigroup associated with automatm Proc. of Syrup. n Mathematical Theory of Automata. Microwave eseareh Institute Symposia Series, Vol. 12, Polytechnic Press, Brooklyn, 1963.

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, Verification