Finite monoids and the fine structure of NC 1
- 1 October 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 35 (4) , 941-952
- https://doi.org/10.1145/48014.63138
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- Non-uniform automata over groupsPublished by Springer Nature ,1987
- Log Depth Circuits for Division and Related ProblemsSIAM Journal on Computing, 1986
- Bounded-depth, polynomial-size circuits for symmetric functionsTheoretical Computer Science, 1985
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- 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
- The dot-depth hierarchy of star-free languages is infiniteJournal of Computer and System Sciences, 1978
- Dot-depth of star-free eventsJournal of Computer and System Sciences, 1971