On Asymptotic Estimates in Switching and Automata Theory

ABSTRACT

Formulas and algorithms have recently been given for calculating the number of symmetry types of functions, networks and automata under various transformation groups. In almost all cases, the computations involved are quite difficult and require the use of a digital computer. In this paper, asymptotic estimates are given for these numbers, which are trivial to compute and which are very accurate in most cases even for small values of the parameters.

REFERENCES

• 1: HARRISON, M. A. The number of transitivity sets of Boolean functios. J. Soc. Indust Appl. Math. 1I (Sept. 1963), 808-828.
• 2: ---. On the classification of Boolean functions by the general linear aid affine groups. J. Soc. Indust. Appl. Math. 12 (June 1964), 285-299.
• 3: Michael A. Harrison, The Number of Classes of Invertible Boolean Functions, Journal of the ACM (JACM), v.10 n.1, p.25-28, Jan. 1963 [doi>10.1145/321150.321152]
• 4: ---. On the number of classes of (n, k) switching networks. J. FranhIin Dst. 276 (Oct. 1963), 313-327.
• 5: ---, A census of finite automata. Can. J. Math. I7 (Jan. 1965), 100-113.
• 6: --. The numlber of symmetry types of Post functions. (In press.)
• 7: LECINEa, R.L. Agine equivalence of switching functions. Doctoral thesis, Harvard U.,. June 1903.
• 8: LOfENS, C.S. Invertible Boolean functions. Trans. IEEE, EC-13, (Oct. 1964), 529-541.
• 9: NEIPORUK, E.I. On the synthesis of networks using linear transformation of variables. Dokl. Akad. Nauk USSR 123 (1958), 610-612; English translation Aut. Express (Apr.. 1959), 12-13.
• 10: PSLYX, G. Sur les types des propositions composes. J. Symb. Logic 5 (1940), 98-103.
• 11: SLEPIAN, D. On the number of symmetry types of Boolean functions of n variables. Can. J. Math. 5 (1953) 185-193.
• 12: STRAZDN, , I.E. On the number of types of-adic functions. Proc. Riga Polytechnic Inslit. X (1963), 167-186.
• 13: LIFSHITZ, E.N. Asymptotic formula for the number of classes of isomorphic autonomous automata with n states. Ukrain Mat. Zh., XVI (1964), 245-246.

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:
Measurement, Performance, Theory, Verification