ε-推移を許したある決定性プッシュダウン変換器対の等価性判定

清野 和司  富田 悦次  若月 光夫  

誌名
電子情報通信学会論文誌 D   Vol.J90-D   No.10   pp.2675-2690
発行日: 2007/10/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: オートマトン・言語理論
キーワード: 
決定性プッシュダウンオートマトン,  決定性プッシュダウン変換器,  等価性判定問題,  

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




あらまし: 
決定性プッシュダウンオートマトン(dpda)の等価性判定問題は,任意のクラスに対して可解であるとの結論が明らかにされたが,その可解性の証明は非常に複雑である.これに対し,筆者らは,dpdaの部分クラスを対象とする,分岐アルゴリズムと名づけた単純で直接的な等価性判定手法を提唱してきた.そして,一方が実時間空スタック受理式である決定性プッシュダウン変換器(dpdt)に対しても,この等価性判定方式が,ほぼ直接的に適応可能であることを既に証明している.本論文では,dpdtに対するその結果を更に拡張し,かつ,その直接的単純性を保ちながら,両者にε-推移を許した ある種のdpdt対に対しても等価性判定を可能とする拡張アルゴリズムを提唱する.