www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/650
Link to publication: http://csdl.computer.org/comp/proceedings/lics/2003/1884/00/18840178abs.htm
ISI #: 000184410600019
ISBN: 0-7695-1884-2
ISSN: 1043-6871
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A140.31 kBAdobe PDF

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