Reachability analysis of real-time systems using time Petri nets
Authors:
- Y. DengYDY. Deng
- G. XuGXG. Xu
- 1 January 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
- Vol. 30 (5) , 725-736
Abstract
Time Petri nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A fundamental and most widely applied method for analyzing Petri nets is reachability analysis. The existing technique for reachability analysis of TPNs, however, is not suitable for timing property verification because one cannot derive end-to-end delay in task execution, an important issue for time-critical systems, from the reachability tree constructed using the technique. In this paper, we present a new reachability based analysis technique for TPNs for timing property analysis and verification that effectively addresses the problem. Our technique is based on a concept called clock-stamped state class (CS-class). With the reachability tree generated based on CS-classes, we can directly compute the end-to-end time delay in task execution. Moreover, a CS-class can be uniquely mapped to a traditional state class based on which the conventional reachability tree is constructed. Therefore, our CS-class-based analysis technique is more general than the existing technique. We show how to apply this technique to timing property verification of the TPN model of a command and control (C2) system.Keywords
This publication has 17 references indexed in Scilit:
- Incremental modeling and verification of flexible manufacturing systemsJournal of Intelligent Manufacturing, 1999
- Introducing software architecture specification and analysis in SAM through an exampleInformation and Software Technology, 1999
- Compositional validation of time-critical systems using communicating time Petri netsIEEE Transactions on Software Engineering, 1995
- Timing constraint Petri nets and their application to schedulability analysis of real-time system specificationsIEEE Transactions on Software Engineering, 1995
- Petri Nets in Flexible and Agile Automation1995
- Analyzing hard-real-time programs for guaranteed schedulabilityIEEE Transactions on Software Engineering, 1991
- Petri nets: Properties, analysis and applicationsProceedings of the IEEE, 1989
- Automatic verification of finite-state concurrent systems using temporal logic specificationsACM Transactions on Programming Languages and Systems, 1986
- Performance Evaluation of Asynchronous Concurrent Systems Using Petri NetsIEEE Transactions on Software Engineering, 1980
- Recoverability of Communication Protocols--Implications of a Theoretical StudyIEEE Transactions on Communications, 1976