Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
- 1 February 1989
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 38 (1) , 150-164
- https://doi.org/10.1016/0022-0000(89)90037-8
Abstract
No abstract availableKeywords
This publication has 30 references indexed in Scilit:
- Finite monoids and the fine structure of NC 1Journal of the ACM, 1988
- Problems complete for deterministic logarithmic spaceJournal of Algorithms, 1987
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1986
- ALGLIB, a simple symbol-manipulation packageCommunications of the ACM, 1985
- A complexity theory based on Boolean algebraJournal of the ACM, 1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- A lower bound on complexity of branching programsPublished by Springer Nature ,1984
- AlternationJournal of the ACM, 1981
- Parallel Prefix ComputationJournal of the ACM, 1980
- Computational Work and Time on Finite MachinesJournal of the ACM, 1972