First-order spectra with one binary predicate

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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