並行計算のコスト理論

日本ソフトウェア科学会　オブジェクト指向計算研究会

並行計算におけるコストを、計算および通信にかかるコストととらえ、空間的コストは考慮せず、時間的コストのみに焦点を与えている。まず、並行計算をラベルつき遷移システムとし、かつ、並行計算のコストをコストつき無限グラフという構造に写像する関数として定義している。その上で、プログラム間の様々なコストに関する順序関係と包含関係を示した。また、様々な並行計算形式系に適用し一般化になることを示した。