Verification of infinite-state dynamic systems using approximate quotient transition systems

From MaRDI portal





Transition systems (TS) describe many dynamical systems, e.g., hybrid systems [see \textit{T. A. Henzinger}, \textit{P.-H. Ho} and \textit{H. Wong-Toi}, IEEE Trans. Autom. Control 43, 540-554 (1998; Zbl 0918.93019)]. They have been successfully applied for the verification of finite-state dynamical systems by \textit{E. M. Clarke}, \textit{E. A. Emerson} and \textit{A. P. Sistla} [ACM Trans. Program. Lang. Syst. 8, 244-263 (1986; Zbl 0591.68027)] through symbolic reachability analysis. For infinite-state TSs the cardinality of a state space makes direct reachability analysis impossible, however. In the present article it is shown that in many cases a solution to the problem can be found on the basis of finite-state simulation of the original system. A labeled TS is a tuple \(T=(Q,\to,Q_0,L^*,L)\), where \(Q\), \(Q_0\) are sets of states, and initial states respectively, \(\to\) specifies transitions (i.e. \(q \to q'\) for \(q,q' \in Q\)), and \(L^*\), \(L\) are the set of labels and a labeling function (\(L:Q \to L^*\)), respectively. In the problem of verification, atomic propositions (AP), whose individual values are either true or false on each state of the TS, are used as labels, so \(L^*=2^{\text{AP}}\). By selecting the initial state \(q_0 \in Q_0\) and unfolding the state transition graph of TS, a computation tree can be obtained with \(q_0\) at the root. A computation tree logic (CTL) formula specifies the evolution of the TS in terms of AP along paths \(q_0 \to q_1 \to \dots \to q_n\dots\) in the computation tree. In the article, a class of ACTL formulae, introduced by \textit{O. Grumberg} and \textit{D. E. Long} [ACM Trans. Program. Lang. Syst. 16, 843-871 (1994)], is considered which must hold for all paths. For example, the stability of dynamical system for each \(q \in Q_0\) can be described by an ACTL formula. A quotient TS (QTS) is a simulation of an infinite-state TS based on a finite partition \(\{P\}\) of the sets \(Q_0\) and \(Q \setminus Q_0\). The QTS is computed by reachability mappings of the original system. It is assumed that all states of the same set \(P\) of the partition have the same labels. So, for ACTL formulae a positive verification of QTS implies it is true for the original TS. The paper represents a bisimulation procedure of refinement of the partition \(\{P\}\). Since in most applications exact QTS cannot be computed, the approximate QTS (AQTS) is introduced. A sufficient condition for an AQTS to be a bisimulation of the infinite-state TS is given. The results are illustrated with an example of a hybrid system.











This page was built for publication: Verification of infinite-state dynamic systems using approximate quotient transition systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4540483)