Computing accumulated delays in real-time systems

R. Alur, C. Courcoubetis, T.A. Henzinger, Formal Methods in System Design 11 (1997) 137–156.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
We present a verification algorithm for duration properties of real-time systems. While simple real-time properties constrain the total elapsed time between events, duration properties constrain the accumulated satisfaction time of state predicates. We formalize the concept of durations by introducing duration measures for timed automata. A duration measure assigns to each finite run of a timed automaton a real number —the duration of the run— which may be the accumulated satisfaction time of a state predicate along the run. Given a timed automaton with a duration measure, an initial and a final state, and an arithmetic constraint, the duration-bounded reachability problem asks if there is a run of the automaton from the initial state to the final state such that the duration of the run satisfies the constraint. Our main result is an (optimal) PSPACE decision procedure for the duration-bounded reachability problem.
Publishing Year
Date Published
1997-01-01
Journal Title
Formal Methods in System Design
Volume
11
Issue
2
Page
137 - 156
IST-REx-ID

Cite this

Alur R, Courcoubetis C, Henzinger TA. Computing accumulated delays in real-time systems. Formal Methods in System Design. 1997;11(2):137-156. doi:10.1023/A:1008626013578
Alur, R., Courcoubetis, C., & Henzinger, T. A. (1997). Computing accumulated delays in real-time systems. Formal Methods in System Design, 11(2), 137–156. https://doi.org/10.1023/A:1008626013578
Alur, Rajeev, Costas Courcoubetis, and Thomas A Henzinger. “Computing Accumulated Delays in Real-Time Systems.” Formal Methods in System Design 11, no. 2 (1997): 137–56. https://doi.org/10.1023/A:1008626013578.
R. Alur, C. Courcoubetis, and T. A. Henzinger, “Computing accumulated delays in real-time systems,” Formal Methods in System Design, vol. 11, no. 2, pp. 137–156, 1997.
Alur R, Courcoubetis C, Henzinger TA. 1997. Computing accumulated delays in real-time systems. Formal Methods in System Design. 11(2), 137–156.
Alur, Rajeev, et al. “Computing Accumulated Delays in Real-Time Systems.” Formal Methods in System Design, vol. 11, no. 2, Springer, 1997, pp. 137–56, doi:10.1023/A:1008626013578.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar