TCTL Model Checking of Time Petri Nets
- 6 July 2009
- journal article
- research article
- Published by Oxford University Press (OUP) in Journal of Logic and Computation
- Vol. 19 (6) , 1509-1540
Abstract
We consider Time Petri Nets (TPN) for which a firing time interval is associated with each transition. State space abstractions for TPN preserving various classes of properties (LTL, CTL and CTL∗) can be computed, in terms of so called state classes. Some methods were proposed to check quantitative timed properties but are not suitable for effective verification of properties of real-life systems. In this article, we consider subscript TCTL for TPN (TPN-TCTL) for which temporal operators are extended with a time interval, specifying a time constraint on the firing sequences. We prove the decidability of TPN-TCTL on bounded TPN and give its theoretical complexity. We propose a zone-based state space abstraction that preserves marking reachability and traces of the TPN. As for Timed Automata (TA), the abstraction may use an over-approximation operator on zones to enforce the termination. A coarser (and efficient) abstraction is then provided and proved exact w.r.t. marking reachability and traces (LTL properties). Finally, we consider a subset of TPN-TCTL properties (TPN-TCTLS) for which it is possible to propose efficient on-the-fly model-checking algorithms. Our approach consists in computing and exploring the zone-based state space abstraction. On a practical point of view, the method is integrated in Romeo [Gardey et al. (2005, Proceedings of 17th International Conference on CAV’05, Vol. 3576 of Lecture Notes in Computer Science, 418–423)], a tool for TPN edition and analysis. In addition to the old features it is now possible to effectively verify a subset of TCTL directly on TPN.Keywords
This publication has 10 references indexed in Scilit:
- Structural translation from Time Petri Nets to Timed AutomataJournal of Systems and Software, 2006
- Model Checking of Time Petri Nets Using the State Class Timed AutomatonDiscrete Event Dynamic Systems, 2006
- Lower and upper bounds in zone-based abstractions of timed automataInternational Journal on Software Tools for Technology Transfer, 2005
- Analyse des réseaux temporels. Calcul des classes enO(n2)et des temps de chemin enO(m ×n)Techniques et Sciences Informatiques, 2003
- Analysis of Timed Systems Using Time-Abstracting BisimulationsFormal Methods in System Design, 2001
- KRONOS: a verification tool for real-time systemsInternational Journal on Software Tools for Technology Transfer, 1997
- Uppaal in a nutshellInternational Journal on Software Tools for Technology Transfer, 1997
- Complexity results for 1-safe netsTheoretical Computer Science, 1995
- A theory of timed automataTheoretical Computer Science, 1994
- Model-Checking in Dense Real-TimeInformation and Computation, 1993