Node Query Preservation for Deterministic Linear Top-Down Tree Transducers

Kazuki Miyahara
(NAIST)
Kenji Hashimoto
(Nagoya University)
Hiroyuki Seki
(Nagoya University)

This paper discusses the decidability of node query preservation problems for XML document transformations. We assume a transformation given by a deterministic linear top-down data tree transducer (abbreviated as DLT^V) and an n-ary query based on runs of a tree automaton. We say that a DLT^V Tr strongly preserves a query Q if there is a query Q' such that for every document t, the answer set of Q' for Tr(t) is equal to the answer set of Q for t. Also we say that Tr weakly preserves Q if there is a query Q' such that for every t_d in the range of Tr, the answer set of Q' for t_d is equal to the union of the answer set of Q for t such that t_d = Tr(t). We show that the weak preservation problem is coNP-complete and the strong preservation problem is in 2-EXPTIME.

In Sebastian Maneth: Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2013), Hanoi, Vietnam, 19/10/2013, Electronic Proceedings in Theoretical Computer Science 134, pp. 27–37.
Published: 20th November 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.134.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org