Universal quantifiers and time complexity of random access machines

DOI10.1007/BF01699468zbMath0578.03022OpenAlexW2006484856MaRDI QIDQ3699679

Etienne Grandjean

Publication date: 1985

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01699468

zbMATH Keywords

alternating spectrageneralised spectraNondeterministic Random Access Machinesprenex first-order sentencesspectrum of a sentence

Mathematics Subject Classification ID

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