同期付生成システム

山下 雅史  阿曽 弘具  稲垣 康善  本多 波雄  

誌名
電子情報通信学会論文誌 D   Vol.J66-D   No.11   pp.1278-1285
発行日: 1983/11/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
本論文では,プロセスの動的な生成,消滅を含む並行処理システムの計算能力や制御機構の解析を目的とする,並行処理システムのモデル,同期付生成システム(Synchronized Production System-SPS)を提案する,SPSは拡張文脈自由文法と状態推移機械の対によって定義されるシステムである.我々はまず,SPSとベクトル加算システム(VAS)の関係を考察し,VASと有限状態SPS(拡張文脈自由文法と有限状態機械(有限オートマトン)の対によって定義されるSPSの部分クラス)とは互いにその動作を模倣できるという意味で同等の能力を持つことを示す.次に,SPSの停止,発散,有界問題を考察し,有限状態SPSに関しては,これらの判定問題はいずれも可解であることを示す.そのために,有限状態SPSのVASによる模倣が用いられ,有限状態SPSに関する上記の判定問題が,VASに関する判定問題に帰着される.