分岐アルゴリズムによる決定性プッシュダウンオートマトン(クラスD0:R0)の等価性判定

富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J61-D   No.10   pp.759-766
発行日: 1978/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
一般の決定性プッシュダウンオートマトン(DPDA)の等価性判定問題は重要な未解決問題であるが,近年種々の方法の考案により,その判定可能な範囲は次第に広げられてきている.特に,最近の大きな成果として大山口,稲垣,本多により,ε-動作なし,空スタック受理式のDPDA(クラスR0)同志,あるいは,更にその一方を空スタック受理式DPDA(クラスD0)としたものに対し,Valiantのparallel stacking法の拡張による等価判定法が発表されている.本論文では,同じくD0:R0のクラスのDPDAを対象としているが,大山口らがクラスR0内の等価性判定のための基本として得た性質をクラスD0:R0の関係へと拡張し,Korenjak & Hopcroftが単純DPDAの等価性判定に用いた分岐アルゴリズムの手法を基礎として,より直接的な判定アルゴリズムを与え,更に広いクラスのものに対する解決のための手立を広げた.ここでは,推移の分岐のチェックをすべき計算状態対をいかにして有限個だけで済ますかが主要点となるが,等価関係式をゆるめた関係式(関係式)を新たに定義し,その関係式をより小さい幾つかの関係式に分割する等価的置換法を導入して,その点を解決している.