From Gamma to CBS: refining multiset transformations with broadcasting processes

This paper presents a novel approach to the problem of implementing programs in Gamma, a computation model of chemical-reaction-like multiset transformations, by translating them into a process calculus with broadcasting communication, CBS. The concurrent message reception of broadcasting communication fits very naturally to the implicit parallelism of the Gamma model. A value that may trigger reactions with several others in the multiset is broadcast to the potential receivers and may thus react with all of them at the same time. This kind of triggering reactions, which we call quasi-unary, is very common in Gamma programs and is found in a large class of problems. The translation constitutes a correct refinement of the Gamma program and offers possibilities for further optimisations for several classes of problems. We address termination of Gamma programs and identify several classes of programs where termination can be detected and practically implemented