| 講演名 | 2000/6/19 COMP2000-18 一般化されたプッシュダウン木変換器の変換能力に関する一考察 袖嶋 嘉哉, 阿部 尚史, 山崎 克典, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 一般化されたプッシュダウン木変換器(g-PDTT)が文献[16]によって導入され, その基本的な性質が明らかにされた.この結果を踏まえて, 本論文では(1)t-変数線形かつt-変数欠落なしという制限のもとで, 下降型プッシュダウン木変換器(t-PDTT)とg-PDTTの変換能力が一致する, (2)弱変数線形かつ弱変数欠落なしかつスタック変数複製なしかつ制限つきεo-変換という制限のもとで, 上昇型プッシュダウン木変換器(b-PDTT)とg-PDTTの変換能力が一致する, 及び(3)g-PDTTの変換能力はt-PDTT及びb-PDTTの変換能力を真に包含することが示されている. |
| 抄録(英) | Generalized pushdown tree transducers(g-PDTTs) have been introdeced in [16] and their fundamental properties have been investigated. According to such results, in this paper we show that (1)the class of translations generated by top-down pushdown tree transducers(t-PDTTS) is indentical to that of g-PDTTs which are restricted to t-variable linear and t-variable nondeletin (2)the class of translations generated by bottom-up pushdown tree transducers(b-PDTTS) is identical to that of g-PDTTs which are restricted to weak variable linear, weak variable nondeleting, stack variable linar, and restricted εo-translation, and (3)the class of translations generated by g-PDTTs properly contains that of t-PDTTs and b-PDTTs. |
| キーワード(和) | プッシュダウン木変換器 / プッシュダウン木オートマン / 文脈自由木文法 |
| キーワード(英) | pushdown tree transducer / pushdown tree automaton / context-free tree grammar |
| 資料番号 | COMP2000-18 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/6/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | COMP2000-18 一般化されたプッシュダウン木変換器の変換能力に関する一考察 |
| サブタイトル（和） | |
| タイトル（英） | Some Notes on Translational Capability of Generalized Pushdown Tree Transducers |
| サブタイトル（和） | |
| キーワード(1)（和/英） | プッシュダウン木変換器 / pushdown tree transducer |
| キーワード(2)（和/英） | プッシュダウン木オートマン / pushdown tree automaton |
| キーワード(3)（和/英） | 文脈自由木文法 / context-free tree grammar |
| 第 1 著者 氏名（和/英） | 袖嶋 嘉哉 / Yoshichika Sodeshima |
| 第 1 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Science, Science University of Tokyo |
| 第 2 著者 氏名（和/英） | 阿部 尚史 / Naofumi Abe |
| 第 2 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Science, Science University of Tokyo |
| 第 3 著者 氏名（和/英） | 山崎 克典 / Katsunori Yamasaki |
| 第 3 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Science, Science University of Tokyo |
| 発表年月日 | 2000/6/19 |
| 資料番号 | COMP2000-18 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 144 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |