Universal quantifiers and time complexity of random access machines

DOI10.1007/BF01699468MaRDI QIDQ3699679zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 3873306
• The Spectra of First-Order Sentences and Computational Complexity
• scientific article; zbMATH DE number 3961589
• COMPLETE SECOND ORDER SPECTRA
• Publication:3030809

Cites work

• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3485739 (Why is no real title available?)
• scientific article; zbMATH DE number 3569862 (Why is no real title available?)
• scientific article; zbMATH DE number 3449753 (Why is no real title available?)
• scientific article; zbMATH DE number 3454792 (Why is no real title available?)
• A hierarchy for nondeterministic time complexity
• A spectrum hierarchy
• Alternation
• Complexity classes and theories of finite models
• Complexity results for classes of quantificational formulas
• Lower bound results on lengths of second-order formulas
• Number of quantifiers is better than number of tape cells
• Separating Nondeterministic Time Complexity Classes
• Some Remarks on Generalized Spectra
• Storage Modification Machines
• The Spectra of First-Order Sentences and Computational Complexity
• The polynomial-time hierarchy
• Time bounded random access machines
• Turing machines and the spectra of first-order formulas
• Upper and lower bounds for first order expressibility

Cited in

(23)

• scientific article; zbMATH DE number 1453080 (Why is no real title available?)
• The quantifier structure of sentences that characterize nondeterministic time complexity
• Graph properties checkable in linear time in the number of vertices
• scientific article; zbMATH DE number 3997169 (Why is no real title available?)
• One unary function says less than two in existential second order logic
• Universal Turing machines with complexity constraint
• Fifty years of the spectrum problem: survey and new results
• COMPLETE SECOND ORDER SPECTRA
• First-order spectra with one variable
• scientific article; zbMATH DE number 3873306 (Why is no real title available?)
• Expressiveness of logic programs under the general stable model semantics
• scientific article; zbMATH DE number 3961589 (Why is no real title available?)
• Investigation of binary spectra by explicit polynomial transformations of graphs
• Invariance properties of RAMs and linear time
• Regular graphs and the spectra of two-variable logic with counting
• scientific article; zbMATH DE number 3878906 (Why is no real title available?)
• First-order spectra with one binary predicate
• Computing on structures
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• On the variable hierarchy of first-order spectra
• A note on first-order spectra with binary relations
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• The Spectra of First-Order Sentences and Computational Complexity

This page was built for publication: Universal quantifiers and time complexity of random access machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3699679)