On the relative complexity of some languages in NC1
- 22 September 1989
- journal article
- Published by Elsevier in Information Processing Letters
- Vol. 32 (5) , 251-256
- https://doi.org/10.1016/0020-0190(89)90052-5
Abstract
No abstract availableThis publication has 11 references indexed in Scilit:
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- Some subclasses of context-free languages in NC1Information Processing Letters, 1988
- Finite monoids and the fine structure of NC 1Journal of the ACM, 1988
- Parallel computation with threshold functionsJournal of Computer and System Sciences, 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
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- On uniform circuit complexityJournal of Computer and System Sciences, 1981
- Language recognition by marking automataInformation and Control, 1972