決定性1カウンタオートマトンに対する直接的な拡張等価性判定アルゴリズム

富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J65-D   No.5   pp.503-510
発行日: 1982/05/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
決定性プッシュダウンオートマトン(dpda)のうち,スタック記号が単一であるものは決定性1カウンタオートマトン(doca)と呼ばれ,その等価性判定の可解性はValiantにより最初に証明された.更に,一方をdpda,もう一方だけがdocaなるように拡張した場合に対する等価性判定問題の可解性も,最近,関本,及び大山口らにより別個に与えられた.本論文では,同じくこの拡張等価性判定問題を対象とするが,そのいずれよりも極めて直接的で簡潔な判定アルゴリズムを提唱する.これは,KorenjakとHopcroftのアルゴリズムを基礎として筆者らがこれまでに開発してきた分岐アルゴリズムによっているものであり,doca同士の等価性判定問題に対しても,Valiantよりも一層単純な解決を与えているものであるともいえよう.