HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 - ENS Paris, 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 Connect in order to contact the contributor
Submitted on : Tuesday, April 7, 2020 - 11:21:28 AM
Last modification on : Thursday, March 17, 2022 - 10:08:54 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

227

Files downloads

99