IEICE TRANSACTIONS on Information
Node Query Preservation for Deterministic Linear Top-Down Tree Transducers
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.512-523
- Publication Date
- 2015/03/01
- Publicized
- 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
Authors
Kazuki MIYAHARA
Nara Institute of Science and Technology
Kenji HASHIMOTO
Nagoya University
Hiroyuki SEKI
Nara Institute of Science and Technology,Nagoya University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuki MIYAHARA, Kenji HASHIMOTO, Hiroyuki SEKI, "Node Query Preservation for Deterministic Linear Top-Down Tree Transducers" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 3, pp. 512-523, March 2015, doi: 10.1587/transinf.2014FCP0014.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014FCP0014/_p
Copy
@ARTICLE{e98-d_3_512,
author={Kazuki MIYAHARA, Kenji HASHIMOTO, Hiroyuki SEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Node Query Preservation for Deterministic Linear Top-Down Tree Transducers},
year={2015},
volume={E98-D},
number={3},
pages={512-523},
abstract={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.},
keywords={},
doi={10.1587/transinf.2014FCP0014},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Node Query Preservation for Deterministic Linear Top-Down Tree Transducers
T2 - IEICE TRANSACTIONS on Information
SP - 512
EP - 523
AU - Kazuki MIYAHARA
AU - Kenji HASHIMOTO
AU - Hiroyuki SEKI
PY - 2015
DO - 10.1587/transinf.2014FCP0014
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - 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.
ER -
English
