Analysis of a class of communicating finite state machines
type: Item
instance of: scholarly article
title: Analysis of a class of communicating finite state machines
zbMATH Open document ID: 0790.68042
DOI: 10.1007/BF01185558
author: Wuxu Peng
author: Sudarshan P. Purushothaman
published in: Acta Informatica
publication date: 1992-01-01T00:00:00Z
review text: The reachability, deadlock detection and unboundedness detection problems are considered for the class of cyclic one-type message networks of communicating finite state machines. We show that all the three problems are effectively solvable by (a) constructing canonical execution event sequences which belong to a context-free language, and (b) showing that the reachability sets are semilinear. Our algorithms have polynomial complexity in terms of size of a global structure of a network, called the shuffle-product. The relationships between general Petri nets and the class of communicating finite state machines considered here are also explored.
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 567325
zbMATH Keywords: concurrency model
zbMATH Keywords: reachability
zbMATH Keywords: deadlock detection
zbMATH Keywords: unboundedness detection
zbMATH Keywords: networks of communicating finite state machines
zbMATH Keywords: polynomial complexity
zbMATH Keywords: shuffle-product
zbMATH Keywords: general Petri nets
MaRDI profile type: Publication
cites work: On Communicating Finite-State Machines
cites work: Q3780411
cites work: Q3862379
cites work: Q3668872
cites work: Properties of Conflict-Free and Persistent Petri Nets
cites work: Q4037389
cites work: Exposure to deadlock for communicating processes is hard to detect
cites work: Q3219122
cites work: Deadlock Detection for a Class of Communicating Finite State Machines
cites work: Unboundedness detection for a class of communicating finite-state machines
description: scientific article; zbMATH DE number 567325