Skip to Main content Skip to Navigation
Conference papers

Successor-Invariant First-Order Logic on Classes of Bounded Degree

Julien Grange 1
1 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of an additional successor relation on the structure is allowed, as long as the validity of formulas is independent on the choice of a particular successor. We show that when the degree is bounded, successor-invariant first-order logic is no more expressive than first-order logic.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-02882118
Contributor : Julien Grange <>
Submitted on : Friday, June 26, 2020 - 2:47:44 PM
Last modification on : Tuesday, August 4, 2020 - 3:49:50 AM

File

succ_inv_bounded_degree.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Julien Grange. Successor-Invariant First-Order Logic on Classes of Bounded Degree. LICS 2020 - Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science, Jul 2020, Saarbrücken, Germany. ⟨10.1145/3373718.3394767⟩. ⟨hal-02882118⟩

Share

Metrics

Record views

53

Files downloads

92