Languages that Capture Complexity Classes
- 1 August 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 16 (4), 760-778
- https://doi.org/10.1137/0216051
Abstract
No abstract availableThis publication has 20 references indexed in Scilit:
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- The Spectra of First-Order Sentences and Computational ComplexitySIAM Journal on Computing, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Number of quantifiers is better than number of tape cellsJournal of Computer and System Sciences, 1981
- AlternationJournal of the ACM, 1981
- Structure and complexity of relational queriesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Universality of data retrieval languagesPublished by Association for Computing Machinery (ACM) ,1979
- One-way log-tape reductionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- The monotone and planar circuit value problems are log space complete for PACM SIGACT News, 1977