Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/41525
Title: | Expressive Completeness of Two-Variable First-Order Logic with Counting for First-Order Logic Queries on Rooted Unranked Trees | Authors: | HELLINGS, Jelle GYSSENS, Marc VAN DEN BUSSCHE, Jan Van Gucht, Dirk |
Issue Date: | 2023 | Publisher: | IEEE | Source: | 2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS, IEEE, p. 1 -13 | Abstract: | We consider the class of finite, rooted, unranked, unordered, node-labeled trees. Such trees are represented as structures with only the parent-child relation, in addition to any number of unary predicates for node labels. We prove that every unary first-order query over the considered class of trees is already expressible in two-variable first-order logic with counting. Somewhat to our surprise, we have not seen this result being conjectured in the extensive literature on logics for trees. Our proof is based on a global variant of local equivalence notions on nodes of trees. This variant applies to entire trees, and involves counting ancestors of locally equivalent nodes. | Notes: | Hellings, J (corresponding author), McMaster Univ, Dept Comp & Software, Hamilton, ON, Canada. jhellings@mcmaster.ca; marc.gyssens@uhasselt.be; jan.vandenbussche@uhasselt.be; vgucht@cs.indiana.edu |
Keywords: | finite-variable logics;counting logics;bounded equivalence of tree nodes;bounded equivalence of trees;Ehrenfeucht-Fraisse game;expressiveness | Document URI: | http://hdl.handle.net/1942/41525 | ISBN: | 979-8-3503-3587-3 | DOI: | 10.1109/LICS56636.2023.10175828 | ISI #: | 001036707700065 | Rights: | 2023 IEEE | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Expressive Completeness of Two-Variable First-Order Logic with Counting for First-Order Logic Queries on Rooted Unranked Trees.pdf Restricted Access | Published version | 1.11 MB | Adobe PDF | View/Open Request a copy |
lics2023_paper_082.pdf | Peer-reviewed author version | 424.58 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.