Using Maximality-Based Labeled Transition System Model for Concurrency Logic Verification

Djamel Eddine Saidouni and Nabil Belala

Computer Vision Group, LIRE Laboratory, University of Mentouri, Algeria

Abstract: In this paper, we show the interest of the maximality-based semantics for the check of concurrent system properties. For this purpose, we use the Maximality-based Labeled Transition System (MLTS) as a behavior model. From this point of view, we can omit action temporal and structural atomicity hypotheses; consequently, we can inherit result of combinatorial state space explosion problem solution based on the use of true concurrency semantics. Properties to be verified are expressed using the Computation Tree Logic (CTL). The main contribution of the paper is to show that model checking algorithms proposed in the literature, which are based on interleaving semantics, may be adapted easily to true concurrency semantics for the verification of new properties classes related to simultaneous progress of actions at different states.

Keywords: Concurrent system, maximality-based semantics, process algebra, model checking, CTL.

Received March 18, 2004; accepted July 8, 2004