On the analysis of cooperation and antagonism in networks of communicating processes
type: Item
instance of: scholarly article
title: On the analysis of cooperation and antagonism in networks of communicating processes
zbMATH Open document ID: 0636.68023
DOI: 10.1007/BF01762125
author: Paris C. Kanellakis
author: Scott A. Smolka
published in: Algorithmica
publication date: 1988-01-01T00:00:00Z
review text: 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 loockout 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.
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4037176
zbMATH Keywords: concurrent programming
zbMATH Keywords: communicating finite state processes
zbMATH Keywords: Potential blocking
zbMATH Keywords: termination
zbMATH Keywords: loockout
zbMATH Keywords: PSPACE-complete
MaRDI profile type: Publication
cites work: Q4091421
cites work: Q3664417
cites work: A Theory of Communicating Sequential Processes
cites work: On Communicating Finite-State Machines
cites work: Automatic verification of finite-state concurrent systems using temporal logic specifications
cites work: Q4198056
cites work: The complexity of problems in systems of communicating sequential processes
cites work: A calculus of communicating systems
cites work: Proving Liveness Properties of Concurrent Programs
cites work: Exposure to deadlock for communicating processes is hard to detect
cites work: Complexity of analyzing the synchronization structure of concurrent programs
full work available at URL: https://doi.org/10.1007/bf01762125
OpenAlex ID: W2021055532
description: scientific article; zbMATH DE number 4037176