First-order spectra with one binary predicate
From MaRDI portal
Publication:1350533
DOI10.1016/0304-3975(95)00112-3zbMath0872.68087OpenAlexW2004142949MaRDI QIDQ1350533
Arnaud Durand, Solomampionona Ranaivoson
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00112-3
Related Items
On spectra of sentences of monadic second order logic with counting ⋮ Linear time and the power of one first-order universal quantifier ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Finite-model theory -- A personal perspective
- First-order spectra with one variable
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Investigation of binary spectra by explicit polynomial transformations of graphs
- A hierarchy for nondeterministic time complexity
- The Spectra of First-Order Sentences and Computational Complexity
- Universal quantifiers and time complexity of random access machines
- Second-order and Inductive Definability on Finite Structures
- Complexity classes and theories of finite models
- A spectrum hierarchy
- Monadic generalized spectra
- Turing machines and the spectra of first-order formulas