First-order spectra with one variable
- 1 April 1990
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 40 (2) , 136-153
- https://doi.org/10.1016/0022-0000(90)90009-a
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- A Natural NP-Complete Problem with a Nontrivial Lower BoundSIAM Journal on Computing, 1988
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- Universal quantifiers and time complexity of random access machinesTheory of Computing Systems, 1985
- The Spectra of First-Order Sentences and Computational ComplexitySIAM Journal on Computing, 1984
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- Complexity classes and theories of finite modelsTheory of Computing Systems, 1981
- Number of quantifiers is better than number of tape cellsJournal of Computer and System Sciences, 1981
- Monadic generalized spectraMathematical Logic Quarterly, 1975
- Turing machines and the spectra of first-order formulasThe Journal of Symbolic Logic, 1974