| 講演名 | 2000/5/11 一般化されたプッシュダウン木変換器の基本的性能 袖嶋 嘉哉, 山崎 克典, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | プッシュダウン木変換器(PDTT)には下降型(t-PDTT)と上昇型(b-PDTT)の2種類が存在するが, その変換能力は一般には異なることが示されている.本論文ではt-PDTTとb-PDTTの能力を包含する一般化されたPDTT(g-PDTT)を新たに導入し, その基本的性質, すなわち(1)最終状態による変換と空スタックによる変換の等価性, (2)任意のg-PDTTに対してそれと等価な単一状態g-PDTTが常に存在すること, (3)g-PDTTにおける標準型の提案, および(4)任意の単一状態g-PDTTに対してそれと等価な線形スタックg-PDTTが常に存在すること等が議論されている. |
| 抄録(英) | The translational capabilities between two pushdown tree transducers(PDTTs), i.e., top-down PDTT(t-PDTT)and a bottom-up PDTT(b-PDTT), are incomparable. In this paper we propose a generalized PDTT(g-PDTT)which has both translatinal capabilities of t-PDTT and those of b-PDTT and show some fundamental properties such that (1)a translation with final state is equivalent to a translation with empty stack, (2)for any g-PDTT M, there always exists a single state g-PDTT M' which is equivalent to M, (3)one standard form of g-PDTT is proposed, (4)for any single state g-PDTT M, there always exists a linear stack g-PDTT M' which is equivalent to M, and so on. |
| キーワード(和) | プッシュダウン木変換器 / プッシュダウン木オートマトン / 文脈自由木文法 |
| キーワード(英) | pushdown tree transducer / pushdown tree automaton / context-free tree grammar |
| 資料番号 | COMP2000-7 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/5/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 一般化されたプッシュダウン木変換器の基本的性能 |
| サブタイトル（和） | |
| タイトル（英） | Fundamental Properties of Generalized Pushdown Tree Transducers |
| サブタイトル（和） | |
| キーワード(1)（和/英） | プッシュダウン木変換器 / pushdown tree transducer |
| キーワード(2)（和/英） | プッシュダウン木オートマトン / pushdown tree automaton |
| キーワード(3)（和/英） | 文脈自由木文法 / context-free tree grammar |
| 第 1 著者 氏名（和/英） | 袖嶋 嘉哉 / Sodeshima Yoshichika |
| 第 1 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Sciences, Science University of Tokyo |
| 第 2 著者 氏名（和/英） | 山崎 克典 / Yamasaki Katsunori |
| 第 2 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Sciences, Science University of Tokyo |
| 発表年月日 | 2000/5/11 |
| 資料番号 | COMP2000-7 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 52 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |