On the analysis of cooperation and antagonism in networks of communicating processes

Publisher Website
Google Scholar
Abstract
We propose a new method for the analysis of cooperative and antagonistic properties of communicating finite state processes (FSPs). This algebraic technique is based on a composition operator and the notion of "possibility equivalence" among FSPs. We demonstrate its utility by showing that potential blocking, lockout, and termination can be efficiently decided for loosely connected networks of tree FSPs. If not all acyclic FSPs are trees, then the cooperative properties become NP-complete and the antagonistic ones PSPACE-complete. For tightly coupled networks of tree FSPs, we also have NP-hardness. For the considerably harder cyclic case, we provide a natural extension of the method as well as a subcase reducible to integer programming with a constant number of variables.

This publication has 0 references indexed in Scilit: