David A. Mix Barrington
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.
- 1 AJTAI, M. Y'.I formulae on finite structures. Ann. Pure Appl. Logic 24 (1983), 1-48.Google Scholar
- 2 BARRINGTON, D. A. Width-3 permutation branching programs. Tech. Memorandum TM-291. M.I.T. Laboratory for Computer Science, Cambridge, Mass., Dec. 1985.Google Scholar
- 3 BARRINGTON, D.A. Bounded-width polynomial-size branching programs recognize exactly those languages in NCj. J. Comput. Syst. Sci., in press. Google Scholar
- 4 BARRINGTON, D.A. Bounded width branching programs. Tech. Rep. TR-361. M.I.T. Laboratory for Computer Science, Cambridge, Mass., 1986. Google Scholar
- 5 BARRINGTON, D. A., AND THb~R~EN, D. Non-uniform automata over groups. In Proceedings of the 14th International Colloquium Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 267. Springer Verlag, Berlin, 1987, pp. 163-173. Google Scholar
- 6 BEAME, P. W., COOK, S. A., AND HOOVER, H.j. Log-depth circuits for division and related problems. SIAM J. Comput. 15 (1986), 994-1003. Google Scholar
- 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.Google Scholar
- 8 Buss, S.R. The Boolean formula value problem is in ALOGTIME. In Proceedings of the 19th ACM Symposium on the Theory of Computing. ACM, New York, 1987, pp. 123-131. Google Scholar
- 9 CHANDRA, A. K., FORTUNE, S., AND LIPTON, R. Unbounded fan-in circuits and associative functions. In Proceedings of the 15th ACM Symposium on Theory of Computing. ACM, New York, 1983, pp. 52-60. Google Scholar
- 10 CHANDRA, A. K., STOCKMEYER, L., AND V|SHKIN, U. Constant-depth reducibility. SIAM J. Comput. 13 (May 1984), 423-439.Google Scholar
- 11 COHEN, R. S., AND BRZOZOWSKI, J.A. Dot-depth of star-free events. J. Comput. Syst. Sci. 5 (1971), 1-16.Google Scholar
- 12 COOK, S.A. The taxonomy of problems with fast parallel algorithms. Inf. Control 64 (Jan. 1985), 2-22. Google Scholar
- 13 EILENBERG, S. Automata, Languages, and Machines, vol. B. Academic Press, Orlando, Fla., 1976. Google Scholar
- 14 FAGIN, R., KLAWE, M. M., PIPPENGER, N. J., AND STOCKMEYER, L. Bounded depth, polynomialsize circuits for symmetric functions. Theoret. Comput. Sci. 36 (1985), 239-250. Google Scholar
- 15 FURST, M., SAXE, J. B., AND SIPSER, M. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17 (1984), 13-27.Google Scholar
- 16 H~STAD, J. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th ACM Symposium on Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York, 1986, pp. 6-20. Google Scholar
- 17 JOHNSON, D.S. The NP-completeness column: An ongoing guide. J. Algorithms 7, 2 (June 1986), 289-305. Google Scholar
- 18 LYNCH, N. Log space recognition and translation of parenthesis grammars. J. ACM 24 (1977), 583-590. Google Scholar
- 19 PARBERRY, I., AND SCHNITGER, G. Parallel computation with threshold functions. In Structure in Complexity Theory. Lecture Notes in Computer Science, No. 223, Springer-Vedag, New York, 1986, pp. 272-290. Google Scholar
- 20 PIN, J.-E., AND STRAUBING, H. Monoids of upper triangular matrices. Colloq. Math. Soc. Jands Bolyai 39 (semigroups), ( 1981 ), 259-272.Google Scholar
- 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.Google Scholar
- 22 SCHOTZENBERGER, M.P. On finite monoids having only trivial subgroups. Inf. Control 8 (1965), 190-194.Google Scholar
- 23 SWSER, M. Borel sets and circuit complexity. In Proceedings of the 15th ACM Symposium on Theory of Computing. ACM, New York, 1983, pp. 61-69. Google Scholar
- 24 SMOLENSKY, R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM, New York, 1987, pp. 77-82. Google Scholar
- 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.Google Scholar
- 26 STRAUBING, H. Semigroups and languages of dot-depth 2. In Proceedings of the 13th ICALP. Lecture Notes in Computer Science, vol. 226. Springer-Verlag, New York, 1986, pp. 416-423. Google Scholar
- 27 STRAUBING, H. Finite monoids and Boolean circuit complexity. Manuscript, Boston College (1986).Google Scholar
- 28 THERIEN, O. Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 ( 1981 ), 195-208.Google Scholar
- 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.Google Scholar
- 30 Y AO, A. C.C. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th IEEE Foundations of Computer Science. IEEE, New York, 1985, pp. 1-19. Google Scholar
- 31 ZASSENHAUS, H.J. The Theory of Groups, 2nd ed. Chelsea, New York, 1958.Google Scholar
Index Terms
- Finite monoids and the fine structure of NC1
Recommendations
Finite monoids and the fine structure of NC1
STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingRecently a new connection was discovered between the parallel complexity class NC1 and the theory of finite automata, in the work of Barrington [Ba86] on bounded width branching programs. There (non-uniform) NC1 was characterized as those languages ...
Nondeterministic NC1 Computation
CCC '96: Proceedings of the 11th Annual IEEE Conference on Computational ComplexityWe define the counting classes #NC1, GapNC1, PNC1 and C=NC1. We prove that boolean circuits, algebraic circuits, programs over nondeterministic finite automata, and programs over constant integer matrices yield equivalent definitions of the latter three ...
Comments