On uniformity within NC1
- 2 December 1990
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 41 (3) , 274-306
- https://doi.org/10.1016/0022-0000(90)90022-d
Abstract
No abstract availableKeywords
This publication has 36 references indexed in Scilit:
- P-uniform circuit complexityJournal of the ACM, 1989
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- Finite monoids and the fine structure of NC 1Journal of the ACM, 1988
- Lower bounds on the size of bounded depth circuits over a complete basis with logical additionMathematical Notes, 1987
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- AlternationJournal of the ACM, 1981
- Families of recognizable sets corresponding to certain varieties of finite monoidsJournal of Pure and Applied Algebra, 1979
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960