Function-algebraic characterizations of log and polylog parallel time
- 1 June 1994
- journal article
- Published by Springer Nature in computational complexity
- Vol. 4 (2) , 175-205
- https://doi.org/10.1007/bf01202288
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- A new recursion-theoretic characterization of the polytime functionscomputational complexity, 1992
- Bounded arithmetic for NC, ALogTIME, L and NLAnnals of Pure and Applied Logic, 1992
- Arithmetizing Uniform NCAnnals of Pure and Applied Logic, 1991
- An algebra and a logic for NC1Information and Computation, 1990
- Sequential, machine-independent characterizations of the parallel complexity classes AlogTIME, AC k , NC k and NCPublished by Springer Nature ,1990
- Subrecursion and lambda representation over free algebrasPublished by Springer Nature ,1990
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- The Boolean formula value problem is in ALOGTIMEPublished by Association for Computing Machinery (ACM) ,1987
- On uniform circuit complexityJournal of Computer and System Sciences, 1981
- AlternationJournal of the ACM, 1981