LIPIcs.CSL.2020.23.pdf
- Filesize: 0.51 MB
- 16 pages
Document
Order-Invariant First-Order Logic over Hollow Trees
Authors
-
Part of:
Volume:
28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-01-06
Cite As Get BibTex
Julien Grange and Luc Segoufin. Order-Invariant First-Order Logic over Hollow Trees. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CSL.2020.23
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Finite Model Theory
Keywords
- order-invariance
- first-order logic
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
- Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, and Luc Segoufin. Locality from Circuit Lower Bounds. SIAM J. Comput., 2012. URL: https://doi.org/10.1137/110856873.
- Michael Benedikt and Luc Segoufin. Regular tree languages definable in FO and in FO_mod. ACM Trans. Comput. Log., 2009. URL: https://doi.org/10.1145/1614431.1614435.
- Michael Benedikt and Luc Segoufin. Towards a characterization of order-invariant queries over tame graphs. J. Symb. Log., 2009. URL: https://doi.org/10.2178/jsl/1231082307.
- Hans L. Bodlaender and Joost Engelfriet. Domino Treewidth. J. Algorithms, 1997. URL: https://doi.org/10.1006/jagm.1996.0854.
- Michael Elberfeld, Marlin Frickenschmidt, and Martin Grohe. Order Invariance on Decomposable Structures. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2016. URL: https://doi.org/10.1145/2933575.2934517.
- Martin Grohe and Thomas Schwentick. Locality of order-invariant first-order formulas. ACM Trans. Comput. Log., 2000. URL: https://doi.org/10.1145/343369.343386.
- Frederik Harwath and Nicole Schweikardt. Regular tree languages, cardinality predicates, and addition-invariant FO. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.489.
- Frederik Harwath and Nicole Schweikardt. On the locality of arb-invariant first-order logic with modulo counting quantifiers. In Computer Science Logic, CSL, 2013. URL: https://doi.org/10.4230/LIPIcs.CSL.2013.363.
- Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. URL: https://doi.org/10.1007/978-3-662-07003-1.
- Hannu Niemistö. On Locality and Uniform Reduction. In 20th IEEE Symposium on Logic in Computer Science, LICS, 2005. URL: https://doi.org/10.1109/LICS.2005.32.
- Nicole Schweikardt and Luc Segoufin. Addition-Invariant FO and Regularity. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS, 2010. URL: https://doi.org/10.1109/LICS.2010.16.
- Thomas Zeume and Frederik Harwath. Order-Invariance of Two-Variable Logic is Decidable. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2016. URL: https://doi.org/10.1145/2933575.2933594.