Structure and Transition-Preserving Functions of Finite Automata

ABSTRACT

Arbitrary finite automata are decomposed into their major substructures, the primaries. Several characterizations of homomorphisms, endomorphisms, isomorphisms, and automorphisms of arbitrary finite automata are presented via reduction to the primaries of the automata. Various characterizations of these transition-preserving functions on singly generated automata are presented and are used as a basis for the reduction. Estimates on the number of functions of each type are given.

REFERENCES

• 1: ARBIB, M.A. Automaton automorphisms. Inform. Contr.; to appear.
• 2: Bruce Barnes, Groups of Automorphisms and Sets of Equivalence Classes of Input for Automata, Journal of the ACM (JACM), v.12 n.4, p.561-565, Oct. 1965 [doi>10.1145/321296.321306]
• 3: BAVEL, Z. On the structure and automorphisms of finite automata. Rep. 192, Dept. d Computer Science, U. of Illinois, Urbana, Oct. 1965.
• 4: BAVEL, Z., AND MULLER, D.E. Reversibility in monadic algebras and automata. 1965 IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, Oct. 1965, pp. 242-247.
• 5: BAYER, R. Automorphism groups and quotients of'strongly connected automata and monadic algebras. 1966 IEEE Conf. Rec. on Switching and Automata Theory, Oct. 1966, pp. 282-297.
• 6: 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]
• 7: A. C. Fleck, On the Automorphism Group of an Automaton, Journal of the ACM (JACM), v.12 n.4, p.566-569, Oct. 1965 [doi>10.1145/321296.321307]
• 8: 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]
• 9: Charles A. Trauth, Jr., Group-Type Automata, Journal of the ACM (JACM), v.13 n.1, p.170-175, Jan. 1966 [doi>10.1145/321312.321327]
• 10: 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]
• 11: 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]
• 12: SHULT, E.E. Private communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

General Terms:
Design, Measurement, Performance, Theory, Verification