Skip to main content
SpringerLink
Log in

NC1: The automata-theoretic viewpoint

  • Published:
computational complexity Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Ajtai, ∑ 11 formulae on finite structures,Ann. Pure and Applied Logic 24 (1983), 1–48.

    Google Scholar 

  2. 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.

    Google Scholar 

  3. 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.

  4. D. A. M. Barrington, N. Immerman, andH. Straubing, On uniformity withinNC 1,J. Computer and Systems Science 41 (1990), 274–306.

    Google Scholar 

  5. D. A. M. Barrington and H. Straubing, Linear-size bounded-width branching programs, Boston College Tech. Rep. BCCS 90-11, October 1990.

  6. D. A. M. Barrington, H. Straubing, and D. Thérien, unpublished manuscript, 1988.

  7. D. A. M. Barrington, H. Straubing, andD. Thérien, Nonuniform automata over groups,Inform. and Computation 89, 2 (1990), 109–132.

    Google Scholar 

  8. D. A. M. Barrington andD. Thérien, Finite Monoids and the Fine Structure ofNC 1,J. Assoc Comput. Mach. 35 (1988), 941–952.

    Google Scholar 

  9. 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.

  10. A. Borodin, D. Dolev, F. Fich, andW. Paul, Bounds for width two branching programs,SIAM J. Comput. 15 (1986), 549–560.

    Google Scholar 

  11. J. A. Brzozowski andI. Simon, Characterizations of locally testable events,Discrete Mathematics 4 (1973), 243–271.

    Google Scholar 

  12. J. A. Brzozowski andF. Fich, Languages ofR-trivial monoids,J. Computer and Systems Science 20 (1980), 32–49.

    Google Scholar 

  13. J. A. Brzozowski andR. Knast, The dot-depth hierarchy of star-free languages is infinite,J. Computer and Systems Science 16 (1978), 37–55.

    Google Scholar 

  14. A. Chandra, M. Furst, and R. Lipton, Multi-party protocol,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 94–99.

  15. S.A. Cook, A taxonomy of problems with fast parallel solutions,Inform. and Computation 64 (1985), 2–22.

    Google Scholar 

  16. S. Eilenberg,Automata, Languages, and Machines, Academic Press, Vol. A (1974), Vol. B (1976).

  17. M. L. Furst, J. B. Saxe, andM. Sipser, Parity, circuits, and the polynomial-time hierarchy,Math. Systems Theory 18 (1984), 13–27.

    Google Scholar 

  18. R. Graham, B. Rothschild, andJ. Spencer,Ramsey Theory, Wiley, New York, 1980.

    Google Scholar 

  19. J. T. Håstad,Computational Limitations for Small-Depth Circuits, Ph. D. Thesis, M.I.T., ACM Doctoral Dissertation Awards, MIT Press, 1987.

  20. J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

  21. D. S. Johnson, TheNP-completeness column: an ongoing guide,J. Algorithms 7 (1986), 289–305.

    Google Scholar 

  22. 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.

    Google Scholar 

  23. K. Ko, Relativized polynomial time hierarchies having exactlyK levels,SIAM J. Comput. 18 (1989), 392–408.

    Google Scholar 

  24. 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.

    Google Scholar 

  25. S. W. Margolis andJ.-E. Pin Inverse semigroups and varieties of finite semigroups,J. Algebra 110 (1987), 306–323.

    Google Scholar 

  26. 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.

    Google Scholar 

  27. R. McNaughton, Algebraic decision procedures for local testability,Math. Systems Theory 8 (1974), 60–76.

    Google Scholar 

  28. 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.

  29. I. Parberry andG. Schnitger, Parallel computation with threshold functions,J. Computer and Systems Science 36 (1988), 278–302.

    Google Scholar 

  30. P. Péladeau,Classes de circuits booléens et variétés de monoïdes, Ph. D. Thesis, Université Paris VI, 1990.

  31. P. Péladeau, Sur le produit avec compteur modulo un nombre premier, to appear inRevue Automatique Informatique et Recherche Opérationnelle-Informatique Théorique.

  32. P. Péladeau, Formulas, regular languages and Boolean circuits, to appear inTheoret. Comput. Science A.

  33. N. Pippenger, On simultaneous resource bounds,Proc. 20th IEEE Ann. Symp. Foundations of Computer Science, 1979, 307–311.

  34. J.-E. Pin,Variétés de langages formels, Masson (1984). English version:Varieties of formal languages, Plenum, New York, 1986.

    Google Scholar 

  35. 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.

    Google Scholar 

  36. J.-E. Pin, H. Straubing, andD. Thérien, Locally trivial categories and unambiguous concatenation,J. Pure Applied Algebra 52 (1988), 297–311.

    Google Scholar 

  37. 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.

    Google Scholar 

  38. M. P. Schützenberger, On finite monoids having only trivial subgroups,Inform. and Control 8 (1965), 190–194.

    Google Scholar 

  39. I. Simon,Hierarchies of events of dot-depth one, Ph. D. Thesis, University of Waterloo, 1972.

  40. M. Sipser, Borel sets and circuit complexity,Proc. 15th Ann. ACM Symp. Theory of Computing, 1983, 61–69.

  41. 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.

  42. H. Straubing,Varieties of recognizable sets whose syntactic monoids contain solvable groups, Ph. D. Thesis, University of California at Berkeley, 1978.

  43. H. Straubing, Constant-depth periodic circuits,Int. J. of Algebra and Computation,1 (1991), 49–88.

    Google Scholar 

  44. D. Thérien,Classification of regular languages by congruences, Ph. D. Thesis, University of Waterloo, 1980.

  45. D. Thérien, Classification of finite monoids: the language approach,Theoret. Comput. Science 14 (1981), 195–208.

    Google Scholar 

  46. D. Thérien, Subword counting and nilpotent groups, inCombinatorics on Words: Progress and Perspectives (L.J. Cummings ed.), Academic Press, 1983, 297–305.

  47. P. Weil, Product of languages with counter, to appear inTheoret. Comput. Science.

  48. A. C. Yao, Separating the polynomial-time hierarchy by oracles,Proc. 26th IEEE Ann. Symp. Foundations of Computer Science, 1985, 1–10.

  49. A. C. Yao, On ACC and threshold circuits,Proc. 31st IEEE Ann. Symp. Foundations of Computer Science, 1990, 619–627.

Download references

Author information

Authors and Affiliations

  1. Departement d'informatique et de recherche opérationnelle, Université de Montréal, succursale A, C.P. 6128, H3C 3J7, Montréal, Québec, Canada

    Pierre McKenzie

  2. School of Computer Science, McGill University, 3480 University Street, H3A 2A7, Montreal, Quebec, Canada

    Pierre Péladeau

  3. School of Computer Science, McGill University, 3480 University Street, H3A 2A7, Montreal, Quebec, Canada

    Denis Therien

Authors
  1. Pierre McKenzie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pierre Péladeau
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Denis Therien
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01212963

Key words

Subject classifications

Search

Navigation