JCSE, vol. 9, no. 1, pp.9-19, 2015

DOI: http://dx.doi.org/10.5626/JCSE.2015.9.1.9o

Improved Region-Based TCTL Model Checking of Time Petri Nets

Mohammad Esmail Esmaili*, Reza Entezari-Maleki, and Ali Movaghar
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

Abstract: The most important challenge in the region-based abstraction method as an approach to compute the state space of time Petri Nets (TPNs) for model checking is that the method results in a huge number of regions, causing a state explosion problem. Thus, region-based abstraction methods are not appropriate for use in developing practical tools. To address this limitation, this paper applies a modification to the basic region abstraction method to be used specially for computing the state space of TPN models, so that the number of regions becomes smaller than that of the situations in which the current methods are applied. The proposed approach is based on the special features of TPN that helps us to construct suitable and small region graphs that preserve the time properties of TPN. To achieve this, we use TPN-TCTL as a timed extension of CTL for specifying a subset of properties in TPN models. Then, for model checking TPN-TCTL properties on TPN models, CTL model checking is used on TPN models by translating TPN-TCTL to the equivalent CTL. Finally, we compare our proposed method with the current region-based abstraction methods proposed for TPN models in terms of the size of the resulting region graph.

Keyword: Time Petri Net; Region abstraction; TCTL; State space; Timed automata; Model checking

Full Paper:   301 Downloads, 2544 View