First-order spectra with one binary predicate

DOI10.1016/0304-3975(95)00112-3MaRDI QIDQ1350533zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 2079026
• A note on first-order spectra with binary relations
• Publication:3030809
• First-order spectra with one variable
• Spectral universality of linear orders with one binary relation
• Ordinal spectra of first-order theories
• On the variable hierarchy of first-order spectra
• scientific article; zbMATH DE number 3961589
• On spectral binary relation
• scientific article; zbMATH DE number 1223621

Cites work

• scientific article; zbMATH DE number 3485739 (Why is no real title available?)
• A hierarchy for nondeterministic time complexity
• A spectrum hierarchy
• Complexity classes and theories of finite models
• Finite-model theory -- A personal perspective
• First-order spectra with one variable
• Investigation of binary spectra by explicit polynomial transformations of graphs
• Monadic generalized spectra
• Second-order and Inductive Definability on Finite Structures
• The Spectra of First-Order Sentences and Computational Complexity
• Turing machines and the spectra of first-order formulas
• Universal quantifiers and time complexity of random access machines
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(14)

• scientific article; zbMATH DE number 2113458 (Why is no real title available?)
• A note on first-order spectra with binary relations
• One unary function says less than two in existential second order logic
• The Spectra of First-Order Sentences and Computational Complexity
• Linear time and the power of one first-order universal quantifier
• First-order spectra with one variable
• scientific article; zbMATH DE number 69385 (Why is no real title available?)
• 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 2079026 (Why is no real title available?)
• On spectra of sentences of monadic second order logic with counting
• scientific article; zbMATH DE number 2121574 (Why is no real title available?)
• Bounded degree and planar spectra
• On the variable hierarchy of first-order spectra

This page was built for publication: First-order spectra with one binary predicate

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