文献

J-GLOBAL ID：201702259871826836   整理番号：17A0517534

非線形トップダウン木変換器において問合せ保存が決定可能であるための十分条件

Sufficient Conditions for the Decidability of Query Preservation of Non-Linear Topdown Tree Transducers

著者 (3件)： 石原鷹 (名古屋大 大学院情報科学研究科) ,  橋本健二 (名古屋大 大学院情報科学研究科) ,  関浩之 (名古屋大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 116  号： 512(SS2016 60-83)  ページ： 109-114  発行年： 2017年03月02日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 問合せ保存とは,変換と問合せに対し,変換前データに対する問合せと同じ結果を得られるような変換後データに対する問合せが存在することをいう。これはスキーマ更新などの領域で重要な性質だが,変換が非線形なクラスの場合には決定不能なことが知られている。本稿では,非線形なクラスの変換に対して問合せ保存が決定可能となるための十分条件を提案し,複製が制限されたある変換クラスに対してこれが決定可能であることを示す。(著者抄録)

シソーラス用語： *XML【マークアップ言語】 ,  文書 ,  *データ変換 ,  *ツリー構造 ,  *問い合わせ言語 ,  十分条件 ,  データ構造 ,  複製 ,  木【グラフ】 ,  データ更新 ,  非線形性
準シソーラス用語： XML文書変換 ,  非線形トップダウン木変換器 ,  問合せ保存 ,  スキーマ ,  順序木

分類 (2件)： 応用プログラミング言語  (JD03052Y) ,  計算理論  (JB02000A)

引用文献 (8件)：

• M. Benedikt, J. Engelfriet, S. Maneth. Determinacy and rewriting of top-down and MSO tree transformations. In Proc. of the 38th MFCS, LNCS 8087, pp. 146-158. Springer, 2013.
• H. Comon, M. Dauchet, R. Gilleron, C. L?ding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata,2007.
• J. Engelfriet. Top-down tree transducers with regular look-ahead. Mathematical Systems Theory, Vol. 10, No. 1, pp. 289-303, 1976.
• J. Engelfriet, S. Maneth, H. Seidl. Deciding equivalence of top-down XML transformations in polynomial time. Journal of Computer and System Sciences, Vol. 75, No. 5, pp.271-286, 2009.
• K. Hashimoto, R. Sawada, Y. Ishihara, H. Seki, T. Fujiwara. Determinacy and subsumption for single-valued bottom-up tree transducers. In Proc. of the 7th LATA, LNCS 7810, pp. 335-346. Springer, 2013.

タイトルに関連する用語 (7件)： 非線形 ,  トップダウン ,  木 ,  変換器 ,  問合せ ,  保存 ,  十分条件