An algebra and a logic for NC1
- 1 July 1990
- journal article
- Published by Elsevier in Information and Computation
- Vol. 87 (1-2) , 241-263
- https://doi.org/10.1016/0890-5401(90)90063-n
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Arithmetizing Uniform NCAnnals of Pure and Applied Logic, 1991
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- Complexity classes and theories of finite modelsTheory of Computing Systems, 1981
- On uniform circuit complexityJournal of Computer and System Sciences, 1981
- Classes of predictably computable functionsTransactions of the American Mathematical Society, 1963
- Decision problems of finite automata design and related arithmeticsTransactions of the American Mathematical Society, 1961
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960