Order-Invariant First-Order Logic over Hollow Trees

Julien Grange 1 Luc Segoufin 1
1 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : We show that the expressive power of order-invariant first-order logic collapses to first-order logic over hollow trees. A hollow tree is an unranked ordered tree where every non leaf node has at most four adjacent nodes: two siblings (left and right) and its first and last children. In particular there is no predicate for the linear order among siblings nor for the descendant relation. Moreover only the first and last nodes of a siblinghood are linked to their parent node, and the parent-child relation cannot be completely reconstructed in first-order.
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-02310749
Contributor : Julien Grange <>
Submitted on : Thursday, October 10, 2019 - 2:14:22 PM
Last modification on : Friday, January 10, 2020 - 3:40:33 PM

File

hollow_tree.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Julien Grange, Luc Segoufin. Order-Invariant First-Order Logic over Hollow Trees. CSL 2020 - 28th annual conference of the European Association for Computer Science Logic, Jan 2020, Barcelona, Spain. pp.1-23, ⟨10.4230/LIPIcs.CSL.2020.23⟩. ⟨hal-02310749⟩

Share

Metrics

Record views

246

Files downloads

227