Search

A reactive system does not terminate and its behaviors are typically defined as a set of infinite sequences of states. In formal verification, a requirement is usually expressed in a logic, and when the models of the logic are also defined as infinite sequences, such as the case for LTL, the satisfaction relation is simply defined by the containment between the set of system behaviors and that of logic models. However, this satisfaction relation does not work for interval temporal logics, where the models can be considered as a set of finite sequences. In this paper, we observe that for different interval based properties, different satisfaction relations are sensible. Two classes of properties are discussed, and accordingly two satisfaction relations are defined, and they are subsequently unified by a more general definition. A tool is developed based on the Spin model checking system to verify the proposed general satisfaction relation for a decidable subset of Discrete Time Duration Calculus.

We formally prove Liu and Layland's classic theorem on the Rate Monotonic Scheduler in Duration Calculus, a real time interval temporal logic. We describe the assumption of the system, the scheduling policy, the requirement, i.e., service is met for the processes before their deadlines, all by Duration Calculus formulae. That a feasibility condition is sufficient is formalised as logical implication. By using the proof system of Duration Calculus, we formally prove that the feasibility condition due to Liu and Layland is sufficient.

In this paper we study the formal modelling and verification of a network player system using Duration Calculus, a real time interval temporal logic. The system is modelled by the conjunction of a number of Duration Calculus formulae each capturing a basic property of the system. That the system satisfies the requirement is expressed by the entailment of the requirement formula from the system formula. We use an automated tool DCValid for verification. DCValid is a model checking tool and it cannot verify our system in the general form, and therefore a special instance is derived from the general model and subsequently checked using DCValid.