Universal quantifiers and time complexity of random access machines
From MaRDI portal
Publication:3699679
DOI10.1007/BF01699468zbMath0578.03022OpenAlexW2006484856MaRDI QIDQ3699679
Publication date: 1985
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01699468
alternating spectrageneralised spectraNondeterministic Random Access Machinesprenex first-order sentencesspectrum of a sentence
Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Invariance properties of RAMs and linear time ⋮ Expressiveness of Logic Programs under the General Stable Model Semantics ⋮ One unary function says less than two in existential second order logic ⋮ First-order spectra with one binary predicate ⋮ Graph properties checkable in linear time in the number of vertices ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ First-order spectra with one variable ⋮ Computing on structures ⋮ Fifty years of the spectrum problem: survey and new results ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting ⋮ Unnamed Item ⋮ Investigation of binary spectra by explicit polynomial transformations of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bound results on lengths of second-order formulas
- Complexity results for classes of quantificational formulas
- Number of quantifiers is better than number of tape cells
- Upper and lower bounds for first order expressibility
- The polynomial-time hierarchy
- A hierarchy for nondeterministic time complexity
- Time bounded random access machines
- The Spectra of First-Order Sentences and Computational Complexity
- Storage Modification Machines
- Alternation
- Complexity classes and theories of finite models
- A spectrum hierarchy
- Separating Nondeterministic Time Complexity Classes
- Some Remarks on Generalized Spectra
- Turing machines and the spectra of first-order formulas
