The Spectra of First-Order Sentences and Computational Complexity

DOI10.1137/0213025zbMath0535.03014OpenAlexW4301523176MaRDI QIDQ3318756

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)

Related Items (10)

Universal quantifiers and time complexity of random access machines ⋮ First-order spectra with one binary predicate ⋮ Graph properties checkable in linear time in the number of vertices ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ First-order spectra with one variable ⋮ Computing on structures ⋮ Fifty years of the spectrum problem: survey and new results ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting ⋮ Unnamed Item

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