The Spectra of First-Order Sentences and Computational Complexity
From MaRDI portal
Publication:3318756
DOI10.1137/0213025zbMATH Open0535.03014OpenAlexW4301523176MaRDI QIDQ3318756FDOQ3318756
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
Recommendations
Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cited In (22)
- 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?)
- Fifty years of the spectrum problem: survey and new results
- COMPLETE SECOND ORDER SPECTRA
- Some remarks on real numbers induced by first-order spectra
- First-order spectra with one variable
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On first-order sentences without finite models
- On the generator problem
- Regular graphs and the spectra of two-variable logic with counting
- Axiomatizing rectangular grids with no extra non-unary relations
- Title not available (Why is that?)
- First-order spectra with one binary predicate
- Computing on structures
- On the variable hierarchy of first-order spectra
- A note on first-order spectra with binary relations
- Bounded degree and planar spectra
- Universal quantifiers and time complexity of random access machines
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)
