Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/947
Title: On the complexity of typechecking top-down XML transformations.
Authors: MARTENS, Wim 
NEVEN, Frank 
Issue Date: 2005
Publisher: Elsevier
Source: THEORETICAL COMPUTER SCIENCE, 336(1). p. 153-180
Abstract: We investigate the typechecking problem for XML transformations: statically verifying that every answer to a transformation 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 input and output schemas. The complexity of the typechecking problems in this scenario ranges from PTIME
Document URI: http://hdl.handle.net/1942/947
ISSN: 0304-3975
e-ISSN: 1879-2294
DOI: 10.1016/j.tcs.2004.10.035
ISI #: 000229422600007
Category: A1
Type: Journal Contribution
Validations: ecoom 2006
Appears in Collections:Research publications

Show full item record

SCOPUSTM   
Citations

30
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

28
checked on May 21, 2022

Page view(s)

48
checked on May 26, 2022

Google ScholarTM

Check

Altmetric


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