Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-02310749
Contributor : Luc Segoufin <>
Submitted on : Tuesday, April 7, 2020 - 11:21:28 AM
Last modification on : Tuesday, September 22, 2020 - 3:52:19 AM

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-02310749v2⟩

Share

Metrics

Record views

39

Files downloads

163