単純決定性プッシュダウンオートマトンの等価性を決定する最短入力記号列長の上界

若月 光夫  富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J75-D1   No.10   pp.950-953
発行日: 1992/10/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: レター
専門分野: 
キーワード: 
決定性プッシュダウンオートマトン,  単純決定性プッシュダウンオートマトン,  単純決定性文法,  等価性判定問題,  言語理論,  

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




あらまし: 
既約な単純DPDA対が等価であるための必要十分条件として,長さがある定数以内の任意の入力記号列に対する動作が,ともに同じであればよいことが知られている.本論文は,このの上界に関するこれまでで最良の結果を明確な証明と共に与える.