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/611

Title: Typechecking Top-Down Uniform Unranked Tree Transducers.
Authors: MARTENS, Wim
NEVEN, Frank
Issue Date: 2003
Publisher: SPRINGER
Citation: DATABASE THEORY ICDT 2003, PROCEEDINGS. p. 64-78
Series/Report: LECTURE NOTES IN COMPUTER SCIENCE, 2572
Abstract: We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as output schemas. The complexity of the typechecking problems in this scenario range from ptime to exptime.
URI: http://hdl.handle.net/1942/611
DOI: 10.1007/3-540-36285-1_5
ISI #: 000181548600005
ISSN: 0302-9743
Category: A1
Type: Journal Contribution
Validation: ecoom, 2004
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A176.45 kBAdobe PDF

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