Typechecking Top-Down Uniform Unranked Tree Transducers Wim Martens and Frank Neven   View Paper (PDF)   Return to Research Papers 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. BIBTEX  Lecture Notes in Computer Science  Publisher: Springer-Verlag Heidelberg  ISSN: 0302-9743  Subject:  Computer Science  Volume 2572 / 2003  Title:  : Database Theory - ICDT 2003: 9th International Conference Siena, Italy, January 8-10, 2003. Proceedings  Editors:  D. Calvanese, M. Lenzerini, R. Motwani (Eds.) :  Chapter: pp. 64 - 78 }, ©2005 Association for Computing Machinery