scientific article; zbMATH DE number 3873306

MaRDI QIDQ3340841zbMATH OpenFDO

Authors Etienne Grandjean

Publication date 1984

zbMATH Keywords

nondeterminismrandom access machinespectrum of a first-order sentenceTuring machineuniversal quantifiers

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Universal quantifiers and time complexity of random access machines
• The Spectra of First-Order Sentences and Computational Complexity
• scientific article; zbMATH DE number 3961589
• COMPLETE SECOND ORDER SPECTRA
• First-order spectra with one variable

Cited in

(13)

• Generic oracles, uniform machines, and codes
• The quantifier structure of sentences that characterize nondeterministic time complexity
• Universal Turing machines with complexity constraint
• A dichotomy result for Ramsey quantifiers
• The Spectra of First-Order Sentences and Computational Complexity
• scientific article; zbMATH DE number 3873293 (Why is no real title available?)
• scientific article; zbMATH DE number 3878906 (Why is no real title available?)
• COMPLETE SECOND ORDER SPECTRA
• Universal quantifiers and time complexity of random access machines
• scientific article; zbMATH DE number 3961589 (Why is no real title available?)
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• scientific article; zbMATH DE number 3997169 (Why is no real title available?)
• scientific article; zbMATH DE number 1453080 (Why is no real title available?)

This page was built for publication:

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