実時間空スタック受理式決定性限定ワンカウンター変換器の多項式時間等価性判定アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
決定性プッシュダウンオートマトン(dpda)の等価性判定問題は,任意のクラスに対する可解性が示されている.しかし,そのアルゴリズムの効率化については,必ずしも十分な解は得られていない.オートマトンや形式文法を基礎とするシステムにおける学習などにおいて,等価性判定は主要な役割を果たし,その効率向上を実現する上で,多項式時間の等価性判定可解性は非常に重要である.本稿では,スタック記号が単一という制限を持つ実時間空スタック受理式決定性限定ワンカウンターオートマトンに出力機構を付与した,実時間空スタック受理式決定性限定ワンカウンター変換器について,筆者らが提唱してきた,分岐アルゴリズムと名付けた単純で直接的な等価性判定手法を用いることにより,その等価性判定が多項式時間で解決できることを示す.
- 社団法人電子情報通信学会の論文
- 2007-10-09
著者
-
富田 悦次
電気通信大学先進アルゴリズム研究ステーション
-
若月 光夫
電気通信大学先進アルゴリズム研究ステーション・電気通信大学情報通信工学科
-
富田 悦次
電気通信大学先進アルゴリズム研究ステーション・中央大学研究開発機構
-
清野 和司
電気通信大学大学院電気通信学研究科情報通信工学専攻
-
富田 悦次
電気通信大学
-
富田 悦次
Department Of Commucations And Systems Engineering The University Of Electro-communications
-
清野 和司
電気通信大学大学院電気通信学研究科情報通信工学専攻:東芝ソリューション株式会社プラットフォームソリューション事業部府中エンジニアリングセンター
-
富田 悦次
電気通信大学|中央大学研究開発機構
-
若月 光夫
電気通信大学大学院情報理工学研究科
-
若月 光夫
電気通信大学先進アルゴリズム研究ステーション・電気通信大学情報理工学研究科
-
若月 光夫
電気通信大学 先進アルゴリズム研究ステーション
-
若月 光夫
電気通信大学
-
若月 光夫
電気通信大学先進アルゴリズム研究ステーション|電気通信大学大学院情報理工学研究科
関連論文
- 最大クリーク問題の多項式時間的可解性の一結果(情報・システム基礎)
- 最大クリーク抽出の単純な最大時間計算量評価と多項式時間的可解性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 最大クリーク抽出問題の理論計算量評価について : グラフの次数を限定した場合
- 準同型写像によって拡張されたある言語クラスに対する正例からの極限同定
- 実時間空スタック受理式決定性限定ワンカウンタ変換器の多項式時間等価性判定(オートマトン・言語理論)
- 最大クリーク問題の多項式時間的可解性の一結果
- 正則言語のある部分クラスに対する正の例からの多項式時間極限同定
- 最大クリーク問題の多項式時間的可解性の改良結果 (Theoretical foundations of computing)
- 第3回UECコンピュータ大貧民大会(UECda-2008)の報告(大会報告)
- 最大クリーク抽出アルゴリズムの共有メモリ型並列計算機上での並列化