Node Query Preservation for Deterministic Linear Top-Down Tree Transducers

Kazuki MIYAHARA  Kenji HASHIMOTO  Hiroyuki SEKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.3   pp.512-523
Publication Date: 2015/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014FCP0014
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
XML,  tree automata,  tree transducers,  run-based queries,  query preservation,  

Full Text: PDF(565.6KB)>>
Buy this Article



Summary: 
This paper discusses the decidability of node query preservation problems for tree transducers. We assume a transformation given by a deterministic linear top-down data tree transducer (abbreviated as DLTV) and an n-ary query based on runs of a tree automaton. We say that a DLTV Tr strongly preserves a query Q if there is a query Q' such that for every tree t, the answer set of Q' for Tr(t) is equal to the answer set of Q for t. We also say that Tr weakly preserves Q if there is a query Q' such that for every t, the answer set of Q' for Tr(t) includes the answer set of Q for t. We show that the weak preservation problem is coNP-complete and the strong preservation problem is in 2-EXPTIME. We also show that the problems are decidable when a given transducer is a functional extended linear top-down data tree transducer with regular look-ahead, which is a more expressive transducer than DLTV.