Skip to Main content Skip to Navigation

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 :
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download
Contributor : Julien Grange <>
Submitted on : Thursday, September 24, 2020 - 10:46:27 AM
Last modification on : Thursday, October 29, 2020 - 3:01:49 PM
Long-term archiving on: : Thursday, December 3, 2020 - 4:41:16 PM


Files produced by the author(s)


  • HAL Id : tel-02947853, version 1



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⟩



Record views


Files downloads