Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/41525
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | HELLINGS, Jelle | - |
dc.contributor.author | GYSSENS, Marc | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.contributor.author | Van Gucht, Dirk | - |
dc.date.accessioned | 2023-10-12T11:45:15Z | - |
dc.date.available | 2023-10-12T11:45:15Z | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2023-10-12T11:34:27Z | - |
dc.identifier.citation | 2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS, IEEE, p. 1 -13 | - |
dc.identifier.isbn | 979-8-3503-3587-3 | - |
dc.identifier.issn | 1043-6871 | - |
dc.identifier.uri | http://hdl.handle.net/1942/41525 | - |
dc.description.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. | - |
dc.description.sponsorship | We thank the reviewers for their constructive comments which helped us to improve the paper. | - |
dc.language.iso | en | - |
dc.publisher | IEEE | - |
dc.rights | 2023 IEEE | - |
dc.subject.other | finite-variable logics | - |
dc.subject.other | counting logics | - |
dc.subject.other | bounded equivalence of tree nodes | - |
dc.subject.other | bounded equivalence of trees | - |
dc.subject.other | Ehrenfeucht-Fraisse game | - |
dc.subject.other | expressiveness | - |
dc.title | Expressive Completeness of Two-Variable First-Order Logic with Counting for First-Order Logic Queries on Rooted Unranked Trees | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.conferencedate | JUN 26-29, 2023 | - |
local.bibliographicCitation.conferencename | 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | - |
local.bibliographicCitation.conferenceplace | Boston Univ, Boston, MA | - |
dc.identifier.epage | 13 | - |
dc.identifier.spage | 1 | - |
local.format.pages | 13 | - |
local.bibliographicCitation.jcat | C1 | - |
dc.description.notes | Hellings, J (corresponding author), McMaster Univ, Dept Comp & Software, Hamilton, ON, Canada. | - |
dc.description.notes | jhellings@mcmaster.ca; marc.gyssens@uhasselt.be; | - |
dc.description.notes | jan.vandenbussche@uhasselt.be; vgucht@cs.indiana.edu | - |
local.publisher.place | 345 E 47TH ST, NEW YORK, NY 10017 USA | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
dc.identifier.doi | 10.1109/LICS56636.2023.10175828 | - |
dc.identifier.isi | 001036707700065 | - |
local.provider.type | wosris | - |
local.bibliographicCitation.btitle | 2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS | - |
local.description.affiliation | [Hellings, Jelle] McMaster Univ, Dept Comp & Software, Hamilton, ON, Canada. | - |
local.description.affiliation | [Gyssens, Marc; Van den Bussche, Jan] Hasselt Univ, Data Sci Inst, Diepenbeek, Belgium. | - |
local.description.affiliation | [Van Gucht, Dirk] Indiana Univ, Luddy Sch Informat Comp & Engn, Bloomington, IN USA. | - |
local.uhasselt.international | yes | - |
item.fulltext | With Fulltext | - |
item.accessRights | Open Access | - |
item.contributor | HELLINGS, Jelle | - |
item.contributor | GYSSENS, Marc | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.contributor | Van Gucht, Dirk | - |
item.fullcitation | HELLINGS, Jelle; GYSSENS, Marc; VAN DEN BUSSCHE, Jan & Van Gucht, Dirk (2023) Expressive Completeness of Two-Variable First-Order Logic with Counting for First-Order Logic Queries on Rooted Unranked Trees. In: 2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS, IEEE, p. 1 -13. | - |
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.