単純決定性プッシュダウンオートマトンの等価性判定の改良分岐アルゴリズムとその最大時間計算量

若月 光夫  富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J74-D1   No.9   pp.595-603
発行日: 1991/09/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマン,言語理論,計算論
キーワード: 


本文: PDF(655.7KB)>>
論文を購入




あらまし: 
筆者らは既に,対象を単純決定性プッシュダウンオートマトン(単純DPDA)に限定した直接的分岐アルゴリズムと呼ぶ等価性判定アルゴリズムを提案しているが,本論文では,対象として与えられた単純DPDAのスタック記号集合に対してスタック同値類と呼ぶ概念を新たに導入することにより,先のアルゴリズムにおけるかぎとなる操作であった対称跳越しを更に拡張し,その適用可能性を増大できるようにしている. この結果,判定木中の節点におけるスタックの高さの上限の減少が達成され,判定操作全体の最大時間計算量の改善が得られている.また,本アルゴリズムにおいては,前処理として各スタック記号に対する最短受理記号列と呼ぶものを求めておくことにより,判定操作自体および正当性の証明の単純化に大きく寄与している.