文章基本信息

标题：May&Must-Equivalence of Shared Variable Parallel Programs in Game Semantics
本地全文：下载
作者：Keisuke Watanabe ; Susumu Nishimura
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2012
卷号：7
期号：4
页码：1432-1441
DOI：10.11185/imt.7.1432
出版社：Information and Media Technologies Editorial Board
摘要：We present a game semantics for an Algol-like language with shared variable parallelism. On contrary to deterministic sequential programs, whose semantics can be characterized by observing termination behaviors, it is crucial for parallel programs to observe not only termination but also divergence, because of nondeterministic scheduling of parallel processes. In order to give a more appropriate foundation for modeling parallelism, we base our development on Harmer's game semantics, which concerns not only may-convergence but also must-convergence for a nondeterministic programming language EIA. The game semantics for the Algol-like parallel language is shown to be fully abstract, which indicates that the parallel command of our Algol-like language adds no extra power than nondeterminism provided by EIA. We also sketch how the equivalence of two parallel programs can be reasoned about based on the game semantical interpretation.
关键词：shared-variable parallelism;may & must-convergence;full abstraction;game semantics