上昇型プッシュダウン木オートマトンと文脈自由木文法の関係
スポンサーリンク
概要
- 論文の詳細を見る
上昇型プッシュダウン木オートマトン(b-PDTA)の受理能力は下降型プッシュダウン木オートマトン(t-PDTA)に比べて低い. したがって, b-PDTAが受理する木言語のクラスと一致するクラスの木言語を受理するある制限を加えたt-PDTA, 及び一致するクラスの木言語を生成する文脈自由木文法(CFTG)のあるサブクラスが定義されることが予想される.このような背景のもとで, 本論文は(1)t-PDTAに制限を加えた, スタック変数複製なしの線形スタックt-PDTAを定義し, b-PDTAが受理する木言語のクラスとスタック変数複製なしの線形スタックt-PDTAが受理する木言語のクラスが一致する, そして(2)CFTGのサブクラスである単一変数CFTGを定義し, b-PDTAが受理する木言語のクラスと単一変数CFTGが生成する木言語のクラスが一致することを示している.
- 社団法人電子情報通信学会の論文
- 2000-07-25
著者
関連論文
- 一般化されたプッシュダウン木変換器の合成と分解に関する一考察
- Recognizable Expressionと有限木オートマトンの等価性
- Recognizable Expression と有限木オートマトンの等価性
- Recognizable Setの記号列表現
- プッシュダウン木変換器の合成と分解に関する一考察
- プッシュダウン木変換器の分類に関する一考察
- 上昇型プッシュダウン木オートマトンと文脈自由木文法の関係
- COMP2000-18 一般化されたプッシュダウン木変換器の変換能力に関する一考察
- 一般化されたプッシュダウン木変換器の基本的性能
- ★付き上昇型プッシュダウン木オートマトンの拡張
- 上昇型プッシュダウン木オートマトンと文脈自由木文法の関係
- 文脈自由木文法の変数に関する一考察
- 上昇型プッシュダウン木オートマトンの一構成法
- 上昇型プッシュダウン木変換器と下降型プッシュダウン木変換器の比較
- 上昇型プッシュダウン木変換器の基本的性質
- 上昇型プッシュダウン木オートマトンの一構成法
- プッシュダウン木オートマトンに対するuvwxy定理
- 上昇型プッシュダウン木オートマトンと下降型プッシュダウン木オートマトンの受理能力の比較について