単純決定性プッシュダウンオートマトンの等価性判定を行う直接的分岐アルゴリズム

若月 光夫  富田 悦次  藤橋 忠悟  

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


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




あらまし: 
本論文では,単純決定性プッシュダウンオートマトン(単純DPDA)の等価性判定問題に対して,対称跳越しとthicknessチェックと呼ぶ操作を導入した新しいアルゴリズムを提唱する.これは先の直接的分岐アルゴリズムを基礎としているが,対象を単純DPDAに限定したため,そこでの主要操作であった跳越し(skipping)を対称的で簡単なものとすることが可能となり,等価性判定アルゴリズム全体の大幅な単純化を達成している.