2026-08-17T07:43:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11666 2024-03-06T10:48:44Z ddc:004 open_access

Order-Invariant First-Order Logic over Hollow Trees Grange, Julien Segoufin, Luc order-invariance first-order logic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Grange and Luc Segoufin 2020 Is Part Of LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2020.23 urn:nbn:de:0030-drops-116661 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.23 eng https://creativecommons.org/licenses/by/3.0/legalcode