The benefits of relaxing punctuality
Alur R, Feder T, Henzinger TA. 1991. The benefits of relaxing punctuality. Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 139–152.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Alur, Rajeev;
Feder, Tomás;
Henzinger, Thomas AISTA 
Abstract
The most natural, compositional, way of modeling real-time systems uses a dense domain for time. The satisfiability of timing constraints that are capable of expressing punctuality in this model, however, is known to be undecidable. We introduce a temporal language that can constrain the time difference between events only with finite, yet arbitrary, precision and show the resulting logic to be EXPSPACE-complete. This result allows us to develop an algorithm for the verification of timing properties of real-time systems with a dense semantics.
Publishing Year
Date Published
1991-01-01
Proceedings Title
Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing
Publisher
ACM
Acknowledgement
We wish to thank an anonymous referee for pointing out the PSPACE-fragment of Section 4.5. T. A. Henzinger was supported in part by the Office of Naval Research Young Investigator award NOOO14-95-l-0520, by the National Science Foundation CAREER award CCR 9501708, by the National Science Foundation grants CCR 92-00794 and CCR 9504469, by the Air Force Office of Scientific Research contract F49620-93-l-0056, and by the Advanced Research Projects Agency grant NAG2-892.
Page
139 - 152
Conference
PODC: Principles of Distributed Computing
Conference Location
Montreal, Canada
Conference Date
1991-08-19 – 1991-08-21
ISBN
IST-REx-ID
Cite this
Alur R, Feder T, Henzinger TA. The benefits of relaxing punctuality. In: Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing. ACM; 1991:139-152. doi:10.1145/227595.227602
Alur, R., Feder, T., & Henzinger, T. A. (1991). The benefits of relaxing punctuality. In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing (pp. 139–152). Montreal, Canada: ACM. https://doi.org/10.1145/227595.227602
Alur, Rajeev, Tomás Feder, and Thomas A Henzinger. “The Benefits of Relaxing Punctuality.” In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, 139–52. ACM, 1991. https://doi.org/10.1145/227595.227602.
R. Alur, T. Feder, and T. A. Henzinger, “The benefits of relaxing punctuality,” in Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, Montreal, Canada, 1991, pp. 139–152.
Alur R, Feder T, Henzinger TA. 1991. The benefits of relaxing punctuality. Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 139–152.
Alur, Rajeev, et al. “The Benefits of Relaxing Punctuality.” Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, ACM, 1991, pp. 139–52, doi:10.1145/227595.227602.
Google Scholar
ISBN Search