# Parametric real-time reasoning

Alur R, Henzinger TA, Vardi M. 1993. Parametric real-time reasoning. Proceedings of the 25th annual ACM symposium on Theory of Computing. STOC: Symposium on the Theory of Computing, 592–601.

Download

**No fulltext has been uploaded. References only!**

*Conference Paper*|

*Published*|

*English*

Author

Alur, Rajeev;
Henzinger, Thomas A

^{ISTA}^{}; Vardi, MosheAbstract

Traditional approaches to the algorithmic verification of real-time systems are limited to checking program correctness with respect to concrete timing properties (e.g., "message delivery within 10 milliseconds"). We address the more realistic and more ambitious problem of deriving symbolic constraints on the timing properties required of real-time systems (e.g., "message delivery within the time it takes to execute two assignment statements"). To model this problem, we introduce parametric timed automata -- finite-state machines whose transitions are constrained with parametric timing requirements. The emptiness question for parametric timed automata is central to the verification problem. On the negative side, we show that in general this question is undecidable. On the positive side, we provide algorithms for checking the emptiness of restricted classes of parametric timed automata. The practical relevance of these classes is illustrated with several verification examples. There remains a gap between the automata classes for which we know that emptiness is decidable and undecidable, respectively, and this gap is related to various hard and open problems of logic and automata theory.

Publishing Year

Date Published

1993-06-01

Proceedings Title

Proceedings of the 25th annual ACM symposium on Theory of Computing

Publisher

ACM

Page

592 - 601

Conference

STOC: Symposium on the Theory of Computing

Conference Location

San Diego, CA, United States of America

Conference Date

1993-05-16 – 1993-05-18

IST-REx-ID

### Cite this

Alur R, Henzinger TA, Vardi M. Parametric real-time reasoning. In:

*Proceedings of the 25th Annual ACM Symposium on Theory of Computing*. ACM; 1993:592-601. doi:10.1145/167088.167242Alur, R., Henzinger, T. A., & Vardi, M. (1993). Parametric real-time reasoning. In

*Proceedings of the 25th annual ACM symposium on Theory of Computing*(pp. 592–601). San Diego, CA, United States of America: ACM. https://doi.org/10.1145/167088.167242Alur, Rajeev, Thomas A Henzinger, and Moshe Vardi. “Parametric Real-Time Reasoning.” In

*Proceedings of the 25th Annual ACM Symposium on Theory of Computing*, 592–601. ACM, 1993. https://doi.org/10.1145/167088.167242.R. Alur, T. A. Henzinger, and M. Vardi, “Parametric real-time reasoning,” in

*Proceedings of the 25th annual ACM symposium on Theory of Computing*, San Diego, CA, United States of America, 1993, pp. 592–601.Alur, Rajeev, et al. “Parametric Real-Time Reasoning.”

*Proceedings of the 25th Annual ACM Symposium on Theory of Computing*, ACM, 1993, pp. 592–601, doi:10.1145/167088.167242.