上昇型プッシュダウン木オートマトンと文脈自由木文法
スポンサーリンク
概要
- 論文の詳細を見る
プッシュダウン木オートマトン(以下PDTAと略記)の概念は,通常のプッシュダウンオートマトンの入力およびプッシュダウン記憶部を木に拡張したものとして提案された.下降型PDTAは,Guessarian,山崎,において,その受理能力と文脈自由木文法(CFTG)の生成能力との等価性が示された.上昇型については,山崎において,その受理能力がCFTGの生成能力より低いことが予想されている.また上昇型の受理能力とCFTGの生成能力の等価性を示したSchimpfによる上昇型PDTAの概念は,山崎によるような従来のPDAを拡張した上昇型PDTAとはことなっている.以下では,スタックを線形のものに制限した上昇型モデルとして超スタック木オートマトン(HSTA)を導入して,閉包性などの性質が従来のPDAの自然な拡張になっていることを確かめ,さらにHSTAの受理能力とCFTGの生成能力とを比較する.
- 社団法人電子情報通信学会の論文
- 1995-09-05
著者
関連論文
- Some families of codes under the pure codes and the bifix codes (Algebras, Languages, Algorithms in Algebraic Systems and Computations)
- Literal shuffle on $\omega$-languages(Semigroups, Formal Languages and Computer Systems)
- 診断結果を論理式で表現した故障診断システム(研究速報)
- d-primitive words and D(1)-concatenated words (Algorithmic and Computational Theory in Algebra and Languages)
- 論理式を用いた故障診断システムについて
- 無向グラフの隣接次数表と最小サイクル表 : 位数制限グラフの同型性
- 隣接次数表による無向グラフが同型であるための十分条件
- 符号のSyntactic congruence
- 非サイクル有向グラフの極大パス被覆を求めるアルゴリズム
- Membership of words in Codes
- Syntactic Congruences of some Codes (Algebraic Systems, Formal Languages and Computations)
- Closure property of Some Codes under Composition (Languages, Algebra and Computer Systems)
- 符号の合成について
- 上昇型プッシュダウン木オートマトンと文脈自由木文法
- ある無限列が表現する実数の集合
- Morphism preserving some kinds of languages (Algebras, Languages, Algorithms and Computations)
- Closure properties of $\omega$-languages under morphism and inverse morphism