| 講演名 | 2016-03-10 On the query preservation for nondeterministic tree transducers 宮原 一喜(奈良先端大), 橋本 健二(名大), 関 浩之(奈良先端大/名大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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. |
| 抄録(英) | 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. |
| キーワード(和) | tree transducers / query rewriting / query preservation |
| キーワード(英) | tree transducers / query rewriting / query preservation |
| 資料番号 | SS2015-79 |
| 発行日 | 2016-03-03 (SS) |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 2016/3/10(から2日開催) |
| 開催地（和） | 沖縄県立宮古青少年の家 |
| 開催地（英） | |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 結縁 祥治(名大) |
| 委員長氏名（英） | Shoji Yuen(Nagoya Univ.) |
| 副委員長氏名（和） | 緒方 和博(北陸先端大) |
| 副委員長氏名（英） | Kazuhiro Ogata(JAIST) |
| 幹事氏名（和） | 小林 隆志(東工大) / 鷲崎 弘宜(早大) |
| 幹事氏名（英） | Takashi Kobayashi(Tokyo Inst. of Tech.) / Hironobu Washizaki(Waseda Univ.) |
| 幹事補佐氏名（和） | 肥後 芳樹(阪大) |
| 幹事補佐氏名（英） | Yoshiki Higo(Osaka Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Software Science |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | On the query preservation for nondeterministic tree transducers |
| サブタイトル（和） | |
| キーワード(1)（和/英） | tree transducers / tree transducers |
| キーワード(2)（和/英） | query rewriting / query rewriting |
| キーワード(3)（和/英） | query preservation / query preservation |
| 第 1 著者 氏名（和/英） | 宮原 一喜 / Kazuki Miyahara |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 第 2 著者 氏名（和/英） | 橋本 健二 / Kenji Hashimoto |
| 第 2 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 第 3 著者 氏名（和/英） | 関 浩之 / Hiroyuki Seki |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学/名古屋大学(略称：奈良先端大/名大) Nara Institute of Science and Technology/Nagoya University(略称：NAIST/Nagoya Univ.) |
| 発表年月日 | 2016-03-10 |
| 資料番号 | SS2015-79 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | SS-508 |
| ページ範囲 | pp.19-24(SS), |
| ページ数 | 6 |
| 発行日 | 2016-03-03 (SS) |