Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/650
Title: | Logical Definability and Query Languages over Unranked Trees. | Authors: | Libkin, Leonid NEVEN, Frank |
Issue Date: | 2003 | Publisher: | IEEE Computer Society | Source: | 18TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS. | Series/Report: | PROCEEDINGS/SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE | Abstract: | Unranked trees, that is, trees with no restriction on the number of children of nodes, have recently attracted much attention, primarily as an abstraction of XML documents. In this paper, we study logical definability over unranked trees, as well as collections of unranked trees, that can be viewed as databases of XML documents. The traditional approach to definability is to view each tree as a structure of a fixed vocabulary, and study the expressive power of various logics on trees. A different approach, based on model theory, considers a structure whose universe is the set of all trees, and studies definable sets and relations; this approach extends smoothly to the setting of definability over collections of trees. We study the latter, model-theoretic approach. We find sets of operations on unranked trees that define regular tree languages, and show that some natural restrictions correspond to logics studied in the context of XML pattern languages. We then look at relational calculi over collections of unranked trees, and obtain quantifier-restriction results that give us bounds on the expressive power and complexity. As unrestricted relational calculi can express problems complete for each level of the polynomial hierarchy, we look at their restrictions, corresponding to the restricted logics over the family of all unranked trees, and find several calculi with low (NC1) data complexity, that can express important XML properties like DTD validation and XPath evaluation. | Document URI: | http://hdl.handle.net/1942/650 | Link to publication/dataset: | http://csdl.computer.org/comp/proceedings/lics/2003/1884/00/18840178abs.htm | ISBN: | 0-7695-1884-2 | ISI #: | 000184410600019 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
lics03.pdf | 140.31 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
2
checked on Oct 14, 2024
Page view(s)
62
checked on Nov 7, 2023
Download(s)
238
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.