EFFECTIVE CHEMISTRY FOR SYNCHRONY AND ASYNCHRONY

摘要

We study from an implementation viewpoint what constitutes a reasonable and effective notion of structural equivalence of terms in a calculus of concurrent processes and propose operational effectiveness criteria in the form of confluence, coherence and standardization properties on an oriented version of the structural laws. We revisit Berry and Boudol's Chemical Abstract Machine (Cham) framework using operational effectiveness criteria. We illustrate our ideas with a new formulation of a Cham for Tccs with external choice, one which is operationally effective unlike previous Cham formulations, and demonstrate that the new Cham is fully abstract with respect to the LTS semantics for Tccs. We then show how this approach extends to the synchronous calculus Sccs, for which a Cham had hitherto not been proposed.