Preview
Unable to display preview. Download preview PDF.
References
M. Ajtai, Σ 11 formulae on finite structures, Annals of Pure and Applied Logic24 (1983), pp. 1–48.
D.A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Proc. of the 18th ACM Symp. on the Theory of Computing (1986), pp. 1–5.
D. Mix Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in NC1, Boston College Technical Report TR-BCCS-88-02, 1988.
D. Mix Barrington, N. Immerman and H. Straubing, On uniformity within NC1, Proc. of the 3rd Annual Conf. on the Structure in Complexity Theory, IEEE Computer Society Press (1988), pp. 47–59.
D.A. Barrington, H. Straubing and D. Thérien, unpublished manuscript, 1988.
D.A. Barrington and D. Thérien, Finite monoids and the fine structure of NC1, Proc. of the 19th ACM Symp. on the Theory of Computing (1987), pp. 101–109.
D.A. Barrington and D. Thérien, Non-uniform automata over groups, Proc. of the 14th International Colloquium on Automata, Languages and Programming, Springer Lecture Notes in Comp. Sci. 267 (1987), pp. 163–173.
A. Borodin, D. Dolev, F. Fich and W. Paul, Bounds for width-two branching programs, Proc. of the 15th ACM Symp. on the Theory of Computing (1983), pp. 97–93.
S.A. Cook, A taxonomy of problems with fast parallel solutions, Information and Computation64 (1985), pp. 2–22.
S. Eilenberg, Automata, Languages and Machines, Academic Press, Vol. A (1974), Vol. B, (1976).
M.L. Furst, J.B. Saxe and M. Sipser, Parity, circuits, and the polynomial-time hierarchy, Proc. of the 22nd IEEE Symp. on the Foundations of Computer Science (1981), pp. 260–270. Journal version Math. Systems Theory18 (1984), 13–27.
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, The NP-completeness column: and ongoing guide, J. of Algorithms7:2 (June 1986), pp. 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.
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, en préparation (1988).
P. Péladeau, Classes of boolean circuits and varieties of finite monoids, draft, May 1988.
J.-E. Pin, Variétés de langages formels, Masson (1984).
J.-E. Pin, H. Straubing and D. Thérien, Locally trivial categories and unambiguous concatenation, J. of Pure and Applied Algebra52 (1988), pp. 297–311.
A.A. Razborov, Lower bounds for the size of circuits of bounded depth with basis {&, ⊕}, Mathematicheskie Zametki41:4 (April 1987), 598–607 (in Russian). English translation Mathematical Notes of the Academy of Sciences of the USSR41:4 (Sept. 1987), pp. 333–338.
M.P. Schützenberger, On finite monoids having only trivial subgroups, Information and Control8 (1965), pp. 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. of the 15th ACM Symp. on the Theory of Computing (1983), pp. 61–69.
R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proc. of the 19th ACM Symp. on the Theory of Computing (1987), pp. 77–82.
H. Straubing, Varieties of recognizable sets whose syntactic monoids contain solvable groups, Ph. D. Thesis, University of California at Berkeley (1978).
D. Thérien, Classification of finite monoids: the language approach, Theoretical Computer Science14 (1981), pp. 195,208.
D. Thérien, Subword counting and nilpotent groups, in Combinatorics on Words: Progress and Perspectives (L.J. Cummings ed.), Academic Press (1983), pp. 297–305.
A. C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. of the 26th IEEE Symp. on the Foundations of Computer Science (1985), pp. 1–10.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
McKenzie, P., Thérien, D. (1989). Automata theory meets circuit complexity. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds) Automata, Languages and Programming. ICALP 1989. Lecture Notes in Computer Science, vol 372. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035785
Download citation
DOI: https://doi.org/10.1007/BFb0035785
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51371-1
Online ISBN: 978-3-540-46201-9
eBook Packages: Springer Book Archive