The Spectra of First-Order Sentences and Computational Complexity

DOI10.1137/0213025MaRDI QIDQ3318756zbMATH OpenOpenAlexFDO

Authors Etienne Grandjean

Publication date 1984

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0213025

zbMATH Keywords

spectrumgeneralized spectrumnon-deterministic Turing machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 3873306
• scientific article; zbMATH DE number 3961589
• First-order spectra with one binary predicate
• Universal quantifiers and time complexity of random access machines
• scientific article; zbMATH DE number 2079026

Cited in

(22)

• The quantifier structure of sentences that characterize nondeterministic time complexity
• A note on first-order spectra with binary relations
• Fifty years of the spectrum problem: survey and new results
• scientific article; zbMATH DE number 3898846 (Why is no real title available?)
• On the generator problem
• On first-order sentences without finite models
• Regular graphs and the spectra of two-variable logic with counting
• Graph properties checkable in linear time in the number of vertices
• scientific article; zbMATH DE number 3873306 (Why is no real title available?)
• First-order spectra with one variable
• Some remarks on real numbers induced by first-order spectra
• scientific article; zbMATH DE number 4019038 (Why is no real title available?)
• scientific article; zbMATH DE number 3961589 (Why is no real title available?)
• First-order spectra with one binary predicate
• scientific article; zbMATH DE number 2079026 (Why is no real title available?)
• Universal quantifiers and time complexity of random access machines
• Computing on structures
• Axiomatizing rectangular grids with no extra non-unary relations
• Bounded degree and planar spectra
• On the variable hierarchy of first-order spectra
• scientific article; zbMATH DE number 3873293 (Why is no real title available?)
• COMPLETE SECOND ORDER SPECTRA

This page was built for publication: The Spectra of First-Order Sentences and Computational Complexity

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