Premium
Syntactic reductions for efficient deadlock analysis
Author(s) -
De Francesco Nicoletta,
Santone Antonella
Publication year - 2002
Publication title -
software testing, verification and reliability
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.216
H-Index - 49
eISSN - 1099-1689
pISSN - 0960-0833
DOI - 10.1002/stvr.252
Subject(s) - deadlock , computer science , automaton , model checking , programming language , state (computer science) , reduction (mathematics) , deadlock prevention algorithms , finite state machine , theoretical computer science , algorithm , mathematics , geometry
A well‐known problem in the verification of concurrent systems based on model checking is state explosion: concurrent systems are often represented by automata with a prohibitive number of states. A reduction technique to reduce state explosion in deadlock checking is presented. The method is based on an automatic syntactic simplification of a calculus of communicating systems (CCS) specification, which keeps the parts of the program structure that may lead to a deadlock and deletes the other parts. Copyright © 2002 John Wiley & Sons, Ltd.