ISSN:
1432-0541
Keywords:
Static analysis
;
Concurrent programming
;
Computational complexity
;
CCS
;
Potential blocking
;
Termination
;
Lockout
;
Finite state process
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 on the notion of possibility equivalence among FSPs. We demonstrate its utility by showing that potential blocking, termination, and lockout can be decided in polynomial time for loosely connected networks of tree FSPs. Potential blocking and termination are examples of cooperative properties, while lockout is an antagonistic one. For loosely connected networks of (the more general) acyclic FSPs, the cooperative properties become NP-complete and the antagonistic ones PSPACE-complete. For tightly coupled networks of tree FSPs, we also have NP-completeness for the cooperative properties. For the harder case of FSPs with cycles, we provide a natural extension of the method.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01762125
Permalink
