文献

J-GLOBAL ID：201202270341556753   整理番号：12A1663254

ゲーム意味論における共有される変数の並列プログラムのmay&must等価性

May & Must-Equivalence of Shared Variable Parallel Programs in Game Semantics

著者 (3件)： WATANABE Keisuke (Kyoto Univ., Kyoko, JPN) ,  WATANABE Keisuke (Tezukayama Junior and Senior High School) ,  NISHIMURA Susumu (Kyoto Univ., Kyoko, JPN)
資料名： 情報処理学会論文誌トランザクション(CD-ROM)  (情報処理学会論文誌 Computer Vision and Applications(CD-ROM))
巻： 2012  号： 1  ページ： ROMBUNNO.PUROGURAMINGU,VOL.5,NO.4,17-26  発行年： 2012年10月15日 
JST資料番号： L7379A  ISSN： 1882-7772  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,共有される変数の並列性を持つAlgolのような言語に対するゲーム意味論を提案した。意味論が終端の振舞いを観測することによって特徴付けることができる決定論的な逐次プログラムに反して,並列プログラムにとっては並列プロセスの非決定性のスケジューリングのために終端だけでなく,分岐も観測することが極めて重要である。並列性のモデリングに対するより適切な基礎を与えるために,非決定性プログラミング言語EIAに対してmay-収束性だけでなく,must-収束性も配慮するHarmerのゲーム意味論に本開発の基礎を置く。Algolのような並列言語のためのゲーム意味論は完全抽象化であることを示した。それはこのAlgolのような並列言語の命令がEIAによって与えられる非決定論以上に特別な能力を追加しないことを指し示す。また,2つの並列プログラムの等価性がゲーム意味論的解釈に基づいてどのように論証され得るかを説明した。(翻訳著者抄録)

シソーラス用語： *並列処理 ,  *高水準言語 ,  *意味論 ,  ゲーム ,  計算機プログラム ,  スケジューリング ,  非決定性 ,  収束 ,  等価性 ,  プログラム理論
準シソーラス用語： *ALGOL ,  *ゲーム意味論 ,  並列プログラム ,  並列言語

分類 (3件)： ディジタル計算機方式一般  (JC02010O) ,  汎用プログラミング言語  (JD03051H) ,  計算理論  (JB02000A)

引用文献 (16件)：

• [1] Herlihy, M. and Shavit, N.: The Art of Multiprocessor Programming,Morgan Kaufmann (2008).
• [2] Hyland, J.M.E. and Ong, C.-H.L.: On Full Abstraction for PCF:I, II, and III, Information and Computation, Vol.163, No.2, pp.285-408 (2000).
• [3] Abramsky, S. and McCusker, G.: Linearity, Sharing and State: A Fully Abstract Game Semantics for Idealized Algol with Active Ex-pressions, Algol-like Languages, O'Hearn, P.W. and Tennent, R.D. (Eds.), Progress in Theoretical Computer Science, Vol.2, pp.297-329, Birkhauser (1997).
• [4] Abramsky, S. and McCusker, G.: Game Semantics, Computational Logic: Proc. 1997 Marktoberdorf Summer School, Schwichtenberg, H. and Berger, U. (Eds.), pp.1-56, Springer-Verlag (1999).
• [5] Ghica, D.R. and Murawski, A.S.: Angelic Semantics of Fine-Grained Concurrency, Annals of Pure and Applied Logic, Vol.151, No.2-3, pp.89-114 (2008).

タイトルに関連する用語 (5件)： ゲーム意味論 ,  共有 ,  変数 ,  並列プログラム ,  等価性