Analysis of a class of communicating finite state machines (Q1323365): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 02:57, 5 March 2024

scientific article
Language Label Description Also known as
English
Analysis of a class of communicating finite state machines
scientific article

    Statements

    Analysis of a class of communicating finite state machines (English)
    0 references
    0 references
    1992
    0 references
    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.
    0 references
    concurrency model
    0 references
    reachability
    0 references
    deadlock detection
    0 references
    unboundedness detection
    0 references
    networks of communicating finite state machines
    0 references
    polynomial complexity
    0 references
    shuffle-product
    0 references
    general Petri nets
    0 references

    Identifiers