ヤノフ形並行プログラム図式の決定可能問題

山下 雅史  稲垣 康善  本多 波雄  

誌名
電子情報通信学会論文誌 D   Vol.J64-D   No.3   pp.228-235
発行日: 1981/03/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
並行プログラム図式(CPS)は,有限固定個数の並行に実行されるプロセスと,それらのプロセス間の同期をとるための有限個の有限状態スケジューラとから構成されるシステムである.CPSは,実際上コンカレントパスカル風の言語で書かれたプログラムをモデル化するのに十分な能力を持っている.本論文では,CPSの図式論ならびに並行処理に関する諸性質の有無に関する決定問題を考察する.すなわち,CPSの各プロセスがヤノフ形である場合(ヤノフ形CPS)について,図式の,自由性,発散性,停止性,同形性,同値性,デッドロックフリー性,相互排除性,決定性(速度独立性)に関する各決定問題を考察する.すなわち,CPSの動作を模倣する非決定性nテープ有限オートマトン(n-NFA)を作り,上記の各決定問題をn-NFAに関する決定問題に帰着し,その可解性を示す.