複数個のプッシュダウンオートマトンの並列動作について

阿江 忠  

誌名
電子情報通信学会論文誌 D   Vol.J59-D   No.9   pp.668-674
発行日: 1976/09/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
複数個のプッシュダウンオートマトンの並列動作を理論的に明確にするため直積と縦続積を有限オートマトンの場合からの拡張として定義し,その能力のクラスを明らかにした.すなわち,
(i) k個の(決定性)プッシュダウンオートマトンの直積(kは2以上の正整数)は1個の(決定性)プッシュダウンオートマトンのクラスと(決定性)線形拘束オートマトンのクラスの中間のクラスに属す.更にこのようなクラスはkの値に応じて無限の階層をなす.
(ii) 2個のプッシュダウンオートマトンの縦続積はチューリング機械と等価である.
更に,帰還積および2方向プッシュダウンオートマトンとの関連についても言及した.