Universal quantifiers and time complexity of random access machines

DOI10.1007/BF01699468zbMATH Open0578.03022OpenAlexW2006484856MaRDI QIDQ3699679FDOQ3699679

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

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

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)

Cites Work

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

Cited In (23)

• Title not available (Why is that?)
• The quantifier structure of sentences that characterize nondeterministic time complexity
• Graph properties checkable in linear time in the number of vertices
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Expressiveness of logic programs under the general stable model semantics
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)