Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
Author:
- 1 February 1989
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 38 (1) , 150-164
Abstract
No abstract availableKeywords
This publication has 29 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 programs1984
- AlternationJournal of the ACM, 1981
- Parallel Prefix ComputationJournal of the ACM, 1980
- Computational Work and Time on Finite MachinesJournal of the ACM, 1972