Regular languages in NC1
- 1 June 1992
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 44 (3) , 478-499
- https://doi.org/10.1016/0022-0000(92)90014-a
Abstract
No abstract availableKeywords
This publication has 18 references indexed in Scilit:
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- Non-uniform automata over groupsInformation and Computation, 1990
- 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
- Unbounded fan-in circuits and associative functionsJournal of Computer and System Sciences, 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
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960