A new extension of activity networks for modeling and verification of timed systems

Authors: HASSAN MOTALLEBI, MOHAMMAD ABDOLLAHI AZGOMI, MOHAMMAD SABER MIRZAEI, ALI MOVAGHAR

Abstract: Stochastic activity networks (SANs) are a well-known petri net-based formalism used for the performance and dependability modeling of a wide range of systems. On the other hand, the growing complexity of timed systems makes it imperative to apply formal analysis techniques in the early stages of the system's development. Finding a suitable framework for the modeling, evaluation, and verification of these systems is still a great challenge. In this paper, we introduce a new formalism named timed activity networks (TANs), which are based on the activity networks that are the nondeterministic settings of the SANs. The advantages of TANs are 2-fold: 1) allowing the construction of more compact petri net-based models of timed systems and 2) allowing the assignment of time intervals to timed activities where the activity completion rates are marking-dependent, which makes TANs a better model for timed systems. Thanks to the presence of the input/output gates, TANs are capable of describing a situation whose specification using petri net-based formalisms was not practical, due to the naivety of the enabling and firing rules in these models. In addition, a great benefit of TANs is the similarity of their primitives and notations to ordinary SANs, which allows us to easily obtaining these 2 models from each other. Accordingly, SANs can be used for performance, and dependability modeling and evaluation, while TANs can be used for the model checking of timed systems. In this paper, we present the definitions, semantics, and model checking techniques of the proposed formalism. In order to model check TAN models, a transformation procedure is given for translating TAN models into the equivalent linear hybrid automaton, which can then be used with the existing techniques and tools.

Keywords: Timed systems, modeling and verification, stochastic activity networks, timed activity networks, polyhedral computations

Full Text: PDF