Finite monoids and the fine structure of NC1

ABSTRACT

Recently a new connection was discovered between the parallel complexity class NC1 and the theory of finite automata in the work of Barrington on bounded width branching programs. There (nonuniform) NC1 was characterized as those languages recognized by a certain nonuniform version of a DFA. Here we extend this characterization to show that the internal structures of NC1 and the class of automata are closely related. In particular, using Thérien's classification of finite monoids, we give new characterizations of the classes AC0, depth-k AC0, and ACC, the last being the AC0 closure of the mod q functions for all constant q. We settle some of the open questions in [3], give a new proof that the dot-depth hierarchy of algebraic automata theory is infinite [8], and offer a new framework for understanding the internal structure of NC1.

REFERENCES

• 1: AJTAI, M. Y'.I formulae on finite structures. Ann. Pure Appl. Logic 24 (1983), 1-48.
• 2: BARRINGTON, D. A. Width-3 permutation branching programs. Tech. Memorandum TM-291. M.I.T. Laboratory for Computer Science, Cambridge, Mass., Dec. 1985.
• 3: David A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences, v.38 n.1, p.150-164, February 1989 [doi>10.1016/0022-0000(89)90037-8]
• 4: D. A. Barrington, BOUNDED WIDTH BRANCHING PROGRAMS, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 5: D. A. Barrington , D. Thérien, Non-uniform automata over groups, 14th International Colloquium on Automata, languages and programming, p.163-173, July 1987, Karlsruhe, Germany
• 6: Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
• 7: BRZOZOWSKI, J. A., AND KNAST, R. The dot-depth hierarchy of star-free languages is infinite. J. Comput. Syst. Sci. 16 (1978), 37-55.
• 8: S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.123-131, January 1987, New York, New York, United States [doi>10.1145/28395.28409]
• 9: Ashok K. Chandra , Steven Fortune , Richard Lipton, Unbounded fan-in circuits and associative functions, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.52-60, December 1983 [doi>10.1145/800061.808732]
• 10: CHANDRA, A. K., STOCKMEYER, L., AND V|SHKIN, U. Constant-depth reducibility. SIAM J. Comput. 13 (May 1984), 423-439.
• 11: COHEN, R. S., AND BRZOZOWSKI, J.A. Dot-depth of star-free events. J. Comput. Syst. Sci. 5 (1971), 1-16.
• 12: Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
• 13: Samuel Eilenberg, Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, 1976
• 14: Ronald Fagin , Maria M. Klawe , Nicholas J. Pippenger , Larry Stockmeyer, Bounded-depth, polynomial-size circuits for symmetric functions, Theoretical Computer Science, v.36 n.2-3, p.239-250, June 1985
• 15: FURST, M., SAXE, J. B., AND SIPSER, M. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17 (1984), 13-27.
• 16: J Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12132]
• 17: David S Johnson, The NP-completeness column: An ongoing guide, Journal of Algorithms, v.7 n.2, p.289-305, June 1986 [doi>10.1016/0196-6774(86)90011-8]
• 18: Nancy Lynch, Log Space Recognition and Translation of Parenthesis Languages, Journal of the ACM (JACM), v.24 n.4, p.583-590, Oct. 1977 [doi>10.1145/322033.322037]
• 19: I Parberry , G Schnitger, Parallel computation with threshold functions, Proc. of the conference on Structure in complexity theory, p.272-290, June 1986, Berkeley, California, United States
• 20: PIN, J.-E., AND STRAUBING, H. Monoids of upper triangular matrices. Colloq. Math. Soc. Jands Bolyai 39 (semigroups), ( 1981 ), 259-272.
• 21: RAZBOROV, A.A. Lower bounds for the size of circuits of bounded depth with basis {&, ~}. Math. Z. 41, 4 (Apr. 1987), 598-607 (in Russian). English translation Math. Notes Acad. Sci. USSR 41, 4 (Sept. 1987), 333-338.
• 22: SCHOTZENBERGER, M.P. On finite monoids having only trivial subgroups. Inf. Control 8 (1965), 190-194.
• 23: Michael Sipser, Borel sets and circuit complexity, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.61-69, December 1983 [doi>10.1145/800061.808733]
• 24: R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
• 25: SPIRA, P.i. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences. Western Periodicals Co., North Hollywood, Calif., 1971, pp. 525-527.
• 26: H Straubing, Semigroups and languages of dot-depth 2, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.416-423, September 1986, Rennes, France
• 27: STRAUBING, H. Finite monoids and Boolean circuit complexity. Manuscript, Boston College (1986).
• 28: THERIEN, O. Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 ( 1981 ), 195-208.
• 29: THI~RIEN, O. Subword counting and nilpotent groups. In Combinatorics on Words: Progress and Perspectives, L J. Cummings, Ed. Academic Press, Orlando, Fla., 1983, pp. 297-305.
• 30: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States
• 31: ZASSENHAUS, H.J. The Theory of Groups, 2nd ed. Chelsea, New York, 1958.

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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models; Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies; Relations among complexity classes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Theory, Verification