Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/11406

Title: Structural Recursion as a Query Language on Lists and Ordered Trees
Authors: Robertson, Edward L.
Saxton, Lawrence V.
Van Gucht, Dirk
Issue Date: 2009
Publisher: SPRINGER
Citation: THEORY OF COMPUTING SYSTEMS, 44 (4). p. 590-619
Abstract: XML query languages need to provide some mechanism to inspect and manipulate nodes at all levels of an input tree. We investigate the expressive power provided in this regard by structural recursion. In particular, we show that the combination of vertical recursion down a tree combined with horizontal recursion across a list of trees gives rise to a robust class of transformations: it captures the class of all primitive recursive queries. Since queries are expected to be computable in at most polynomial time for all practical purposes, we next identify a restriction of structural recursion that captures the polynomial time queries. We also give corresponding results for list-based complex objects.
Notes: [Vansummeren, Stijn] Hasselt Univ, B-3560 Diepenbeek, Belgium. [Vansummeren, Stijn] Translat Univ Limburg, B-3560 Diepenbeek, Belgium. [Saxton, Lawrence V.] Univ Regina, Regina, SK S4S 0A2, Canada. [Robertson, Edward L.; Van Gucht, Dirk] Indiana Univ, Bloomington, IN USA. edrbtsn@cs.indiana.edu; saxton@cs.uregina.ca; vgucht@cs.indiana.edu; stijn.vansummeren@uhasselt.be
URI: http://hdl.handle.net/1942/11406
DOI: 10.1007/s00224-008-9110-5
ISI #: 000265399700005
ISSN: 1432-4350
Category: A1
Type: Journal Contribution
Validation: ecoom, 2010
Appears in Collections: Research publications

Files in This Item:

There are no files associated with this item.

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