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
Source: DATABASE THEORY ICDT 2003, PROCEEDINGS. p. 64-78
Series/Report: LECTURE NOTES IN COMPUTER SCIENCE
Series/Report no.: 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.
Document URI: http://hdl.handle.net/1942/611
ISSN: 0302-9743
DOI: 10.1007/3-540-36285-1_5
ISI #: 000181548600005
Category: A1
Type: Journal Contribution
Validations: ecoom 2004
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
30 tc.pdf176.45 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

35
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

30
checked on May 14, 2022

Page view(s)

224
checked on Feb 24, 2022

Download(s)

302
checked on Feb 24, 2022

Google ScholarTM

Check

Altmetric


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