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: 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 SizeFormat 
lics03.pdf140.31 kBAdobe PDFView/Open
Show full item record

WEB OF SCIENCETM
Citations

2
checked on May 22, 2022

Page view(s)

46
checked on May 25, 2022

Download(s)

176
checked on May 25, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.