Temporal proof methodologies for timed transition systems

T.A. Henzinger, Z. Manna, A. Pnueli, Information and Computation 112 (1994) 273–337.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
We extend the specification language of temporal logic, the corresponding verification framework, and the underlying computational model to deal with real-;time properties of reactive systems. The abstract notion of timed transition systems generalizes traditional transition systems conservatively: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound timing constraints on transitions. This framework can model real-time systems that communicate either through shared variables or by message passing and real-time issues such as timeouts, process priorities (interrupts), and process scheduling. We exhibit two styles for the specification of real-time systems. While the first approach uses time-bounded versions of the temporal operators, the second approach allows explicit references to time through a special clock variable. Corresponding to the two styles of specification, we present and compare two different proof methodologies for the verification of timing requirements that are expressed in these styles. For the bounded-operator style, we provide a set of proof rules for establishing bounded-invariance and bounded-responce properties of timed transition systems. This approach generalizes the standard temporal proof rules for verifying invariance and response properties conservatively. For the explicit-clock style, we exploit the observation that every time-bounded property is a safety property and use the standard temporal proof rules for establishing safety properties.
Publishing Year
Date Published
1994-01-01
Journal Title
Information and Computation
Volume
112
Issue
2
Page
273 - 337
IST-REx-ID

Cite this

Henzinger TA, Manna Z, Pnueli A. Temporal proof methodologies for timed transition systems. Information and Computation. 1994;112(2):273-337. doi:10.1006/inco.1994.1060
Henzinger, T. A., Manna, Z., & Pnueli, A. (1994). Temporal proof methodologies for timed transition systems. Information and Computation, 112(2), 273–337. https://doi.org/10.1006/inco.1994.1060
Henzinger, Thomas A, Zohar Manna, and Amir Pnueli. “Temporal Proof Methodologies for Timed Transition Systems.” Information and Computation 112, no. 2 (1994): 273–337. https://doi.org/10.1006/inco.1994.1060.
T. A. Henzinger, Z. Manna, and A. Pnueli, “Temporal proof methodologies for timed transition systems,” Information and Computation, vol. 112, no. 2, pp. 273–337, 1994.
Henzinger TA, Manna Z, Pnueli A. 1994. Temporal proof methodologies for timed transition systems. Information and Computation. 112(2), 273–337.
Henzinger, Thomas A., et al. “Temporal Proof Methodologies for Timed Transition Systems.” Information and Computation, vol. 112, no. 2, Elsevier, 1994, pp. 273–337, doi:10.1006/inco.1994.1060.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar