Abstract
Concepts from the algebraic theory of finite automata are carried over to the “program-over-monoid” setting which underlies Barrington's algebraic characterization of the complexity classNC 1. Sets of languages accepted by polynomial-length programs over finite monoids drawn from a given monoid variety V emerge as fundamental language classes: as V ranges over monoid varieties these classes capture and indeed refine the usual bounded-depth circuit parametrization of nonuniformNC 1 subclasses. Here it is shown that any two separable such language classes can be separated by a regular language. Basic properties of these language classes are exhibited. New conditions are given under which distinct varieties lead to equal or to distinct language classes, thus sharpening our knowledge of the internal structure of non-uniformNC 1. The paper concludes with the statement of a conjecture whose proof would refine and then resolve most open questions about this internal structure.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ajtai, ∑ 11 formulae on finite structures,Ann. Pure and Applied Logic 24 (1983), 1–48.
D. A. M. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages inNC 1,J. Computer and Systems Science 38 (1989), 150–164.
D. A. M. Barrington, K. Compton, H. Straubing, and D. Thérien, Regular languages inNC 1, Boston College Technical Report TR-BCCS-88-02, 1988, to appear inJ. Computer and Systems Science.
D. A. M. Barrington, N. Immerman, andH. Straubing, On uniformity withinNC 1,J. Computer and Systems Science 41 (1990), 274–306.
D. A. M. Barrington and H. Straubing, Linear-size bounded-width branching programs, Boston College Tech. Rep. BCCS 90-11, October 1990.
D. A. M. Barrington, H. Straubing, and D. Thérien, unpublished manuscript, 1988.
D. A. M. Barrington, H. Straubing, andD. Thérien, Nonuniform automata over groups,Inform. and Computation 89, 2 (1990), 109–132.
D. A. M. Barrington andD. Thérien, Finite Monoids and the Fine Structure ofNC 1,J. Assoc Comput. Mach. 35 (1988), 941–952.
F. Bédard, F. Lemieux, and P. McKenzie, Extensions to Barrington'sM-program model,Proc. of the 5th Annual Structure in Complexity Theory Conf., IEEE Computer Society Press, 1990, 200–209, to appear inTheoret. Comput. Science.
A. Borodin, D. Dolev, F. Fich, andW. Paul, Bounds for width two branching programs,SIAM J. Comput. 15 (1986), 549–560.
J. A. Brzozowski andI. Simon, Characterizations of locally testable events,Discrete Mathematics 4 (1973), 243–271.
J. A. Brzozowski andF. Fich, Languages ofR-trivial monoids,J. Computer and Systems Science 20 (1980), 32–49.
J. A. Brzozowski andR. Knast, The dot-depth hierarchy of star-free languages is infinite,J. Computer and Systems Science 16 (1978), 37–55.
A. Chandra, M. Furst, and R. Lipton, Multi-party protocol,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 94–99.
S.A. Cook, A taxonomy of problems with fast parallel solutions,Inform. and Computation 64 (1985), 2–22.
S. Eilenberg,Automata, Languages, and Machines, Academic Press, Vol. A (1974), Vol. B (1976).
M. L. Furst, J. B. Saxe, andM. Sipser, Parity, circuits, and the polynomial-time hierarchy,Math. Systems Theory 18 (1984), 13–27.
R. Graham, B. Rothschild, andJ. Spencer,Ramsey Theory, Wiley, New York, 1980.
J. T. Håstad,Computational Limitations for Small-Depth Circuits, Ph. D. Thesis, M.I.T., ACM Doctoral Dissertation Awards, MIT Press, 1987.
J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
D. S. Johnson, TheNP-completeness column: an ongoing guide,J. Algorithms 7 (1986), 289–305.
S. C. Kleene, Representation of events in nerve nets and finite automata,Automata Studies, (Shannon and McCarthy, eds), Princeton University Press, Princeton, 1954, pp 3–41.
K. Ko, Relativized polynomial time hierarchies having exactlyK levels,SIAM J. Comput. 18 (1989), 392–408.
K. Krohn andJ. L. Rhodes, Algebraic theory of machines, I. Prime decomposition theorem for finite semigroups and machines,Trans. Amer. Math. Soc. 116 (1965), 450–464.
S. W. Margolis andJ.-E. Pin Inverse semigroups and varieties of finite semigroups,J. Algebra 110 (1987), 306–323.
P. McKenzie andD. Thérien, Automata theory meets circuit complexity, Proc. 16th Intern. Colloquium on Automata, Languages and Programming,Springer Lecture Notes in Comp. Sci. 372, 1989, 589–602.
R. McNaughton, Algebraic decision procedures for local testability,Math. Systems Theory 8 (1974), 60–76.
J. Mullins,Programmes sur des petites variétés de monoïdes apériodiques, Mémoire de maîtrise, Dép. I.R.O., Univ. de Montréal, 1988.
I. Parberry andG. Schnitger, Parallel computation with threshold functions,J. Computer and Systems Science 36 (1988), 278–302.
P. Péladeau,Classes de circuits booléens et variétés de monoïdes, Ph. D. Thesis, Université Paris VI, 1990.
P. Péladeau, Sur le produit avec compteur modulo un nombre premier, to appear inRevue Automatique Informatique et Recherche Opérationnelle-Informatique Théorique.
P. Péladeau, Formulas, regular languages and Boolean circuits, to appear inTheoret. Comput. Science A.
N. Pippenger, On simultaneous resource bounds,Proc. 20th IEEE Ann. Symp. Foundations of Computer Science, 1979, 307–311.
J.-E. Pin,Variétés de langages formels, Masson (1984). English version:Varieties of formal languages, Plenum, New York, 1986.
J.-E. Pin, Finite group topology andp-adic topology for free monoids, Proc. 12th Intern. Colloquium on Automata, Languages and Programming,Springer Lecture Notes in Comp. Sci. 194, 1985, 445–455.
J.-E. Pin, H. Straubing, andD. Thérien, Locally trivial categories and unambiguous concatenation,J. Pure Applied Algebra 52 (1988), 297–311.
A. A. Razborov, Lower bounds for the size of circuits of bounded depth with basis {&, ⊕}Mathematicheskie Zametki 41:4 (April 1987), 598–607 (in Russian). English translationMathematical Notes of the Academy of Sciences of the USSR 41 (1987), 333–338.
M. P. Schützenberger, On finite monoids having only trivial subgroups,Inform. and Control 8 (1965), 190–194.
I. Simon,Hierarchies of events of dot-depth one, Ph. D. Thesis, University of Waterloo, 1972.
M. Sipser, Borel sets and circuit complexity,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 61–69.
R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity,Proc. 19th Ann. ACM Symp. Theory of Computing, 1987, 77–82.
H. Straubing,Varieties of recognizable sets whose syntactic monoids contain solvable groups, Ph. D. Thesis, University of California at Berkeley, 1978.
H. Straubing, Constant-depth periodic circuits,Int. J. of Algebra and Computation,1 (1991), 49–88.
D. Thérien,Classification of regular languages by congruences, Ph. D. Thesis, University of Waterloo, 1980.
D. Thérien, Classification of finite monoids: the language approach,Theoret. Comput. Science 14 (1981), 195–208.
D. Thérien, Subword counting and nilpotent groups, inCombinatorics on Words: Progress and Perspectives (L.J. Cummings ed.), Academic Press, 1983, 297–305.
P. Weil, Product of languages with counter, to appear inTheoret. Comput. Science.
A. C. Yao, Separating the polynomial-time hierarchy by oracles,Proc. 26th IEEE Ann. Symp. Foundations of Computer Science, 1985, 1–10.
A. C. Yao, On ACC and threshold circuits,Proc. 31st IEEE Ann. Symp. Foundations of Computer Science, 1990, 619–627.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
McKenzie, P., Péladeau, P. & Therien, D. NC1: The automata-theoretic viewpoint. Comput Complexity 1, 330–359 (1991). https://doi.org/10.1007/BF01212963
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01212963