For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Query Rewriting for Nondeterministic Tree Transducers
Kazuki MIYAHARA Kenji HASHIMOTO Hiroyuki SEKI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/06/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Formal Approach)
Category: Formal Methods
tree transducers, query rewriting, query preservation,
Full Text: PDF(432.9KB)>>
We consider the problem of deciding whether a query can be rewritten by a nondeterministic view. It is known that rewriting is decidable if views are given by single-valued non-copying devices such as compositions of single-valued extended linear top-down tree transducers with regular look-ahead, and queries are given by deterministic MSO tree transducers. In this paper, we extend the result to the case that views are given by nondeterministic devices that are not always single-valued. We define two variants of rewriting: universal preservation and existential preservation, and discuss the decidability of them.