Skip to Main content Skip to Navigation
Theses

On the Expressive Power of Invariant Logics over Sparse Classes of Structures

Julien Grange 1, 2
1 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : This thesis focuses on the expressive power of two invariant logics: successor-invariant first-order logic, Succ-inv FO, and order-invariant first-order logic, <-inv FO. In these formalisms, on top of plain first-order logic, FO, an access to an additional successor relation (for Succ-inv FO) or linear order relation (for <-inv FO) on structures is granted, provided that the evaluation of sentences does not depend on the choice of a particular relation. It is well known that both Succ-inv FO and <-inv FO are more expressive than FO in general. However, if one considers only trees, these logics are no more expressive than plain FO. The two main results of this thesis extend the classes of structures on which these invariant logics collapse to FO. First, we prove that Succ-inv FO is no more expressive than FO on classes of bounded degree. For that, we show how successor relations preserving FO-similarity can be constructed. Second, we define a new class of structures, that of hollow trees. A hollow tree can be seen as an unranked tree, where a parent is only linked to its leftmost and rightmost children. Elements of a siblinghood are linearly related through another binary relation, which is symmetric. The notion of hollow trees is a generalization of ranked trees, and we believe it to be a gateway to structures of pathwidth 2. We show that <-inv FO collapses to FO on the class of hollow trees.
Document type :
Theses
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download

https://hal.inria.fr/tel-02947853
Contributor : Julien Grange <>
Submitted on : Thursday, September 24, 2020 - 10:46:27 AM
Last modification on : Wednesday, October 14, 2020 - 3:48:50 AM

File

these_jgrange.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-02947853, version 1

Collections

Citation

Julien Grange. On the Expressive Power of Invariant Logics over Sparse Classes of Structures. Logic in Computer Science [cs.LO]. ENS Paris, 2020. English. ⟨tel-02947853⟩

Share

Metrics

Record views

50

Files downloads

86