Abstract
In previous work, the timed logic TCTL was extended with an “almost everywhere” Until modality which abstracts negligible sets of positions (i.e. with a null duration) along a run of a timed automaton. We propose here an extension of this logic with more powerful modalities, in order to specify properties abstracting transient states, which are events that last for less than k time units. Our main result is that model-checking is still decidable and PSPACE-complete for this extension. On the other hand, a second semantics is defined, in which we consider the total duration where the property does not hold along a run. In this case, we prove that model-checking is undecidable.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alur, R., Courcoubetis, C., Dill, D.: Model-checking in dense real-time. Information and Computation 104(1), 2–34 (1993)
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T.A., Ho, P.-H., Nicollin, X., Olivero, A., Sifakis, J., Yovine, S.: The algorithmic analysis of hybrid systems. Theoretical Computer Science 138(1), 3–34 (1995)
Alur, R., Courcoubetis, C., Henzinger, T.A.: Computing accumulated delays in real-time systems. Formal Methods in System Design 11(2), 137–156 (1997)
Alur, R., Dill, D.: A theory of timed automata. Theoretical Computer Science 126(2), 183–235 (1994)
Alur, R., Feder, T., Henzinger, Th.A.: The benefits of relaxing punctuality. J. ACM 43(1), 116–146 (1996)
Alur, R., Henzinger, Th.A.: Logics and models of real-time: a survey. In: Huizing, C., de Bakker, J.W., Rozenberg, G., de Roever, W.-P. (eds.) REX 1991. LNCS, vol. 600, pp. 74–106. Springer, Heidelberg (1992)
Alur, R., La Torre, S., Pappas, G.J.: Optimal paths in weighted timed automata. In: Di Benedetto, M.D., Sangiovanni-Vincentelli, A.L. (eds.) HSCC 2001. LNCS, vol. 2034, pp. 49–62. Springer, Heidelberg (2001)
Behrmann, G., Fehnker, A., Hune, Th., Larsen, K.G., Pettersson, P., Romijn, J., Vaandrager, F.: Minimum-cost reachability for priced timed automata. In: Di Benedetto, M.D., Sangiovanni-Vincentelli, A.L. (eds.) HSCC 2001. LNCS, vol. 2034, pp. 147–161. Springer, Heidelberg (2001)
Belmokadem, H., Bérard, B., Bouyer, P., Laroussinie, F.: A New Modality for Almost Everywhere Propeties in Timed Automata. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 110–124. Springer, Heidelberg (2005)
Bouyer, P., Brihaye, T., Markey, N.: Improved Undecidability Results on Priced Timed Automata. Information Processing Letters 98(5), 188–194 (2006)
Bouyer, P., Brinksma, E., Larsen, K.G.: Staying alive as cheaply as possible. In: Alur, R., Pappas, G.J. (eds.) HSCC 2004. LNCS, vol. 2993, pp. 203–218. Springer, Heidelberg (2004)
Brihaye, T., Bruyère, V., Raskin, J.-F.: Model-checking for weighted timed automata. In: Lakhnech, Y., Yovine, S. (eds.) FORMATS 2004 and FTRTFT 2004. LNCS, vol. 3253, pp. 277–292. Springer, Heidelberg (2004)
Bruyère, V., Dall’Olio, E., Raskin, J.-F.: Durations, parametric model-checking in timed automata with presburger arithmetic. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 687–698. Springer, Heidelberg (2003)
Chaochen, Z., Hoare, C., Ravn, A.: A calculus of duration. Information Processing Letters 40(5), 269–276 (1991)
Henzinger, T.A., Ho, P.-H., Wong-Toi, H.: HyTech: A model-checker for hybrid systems. Journal of Software Tools for Technology Transfer 1(1–2), 110–122 (1997)
Henzinger, Th.A.: The theory of hybrid automata. In: Proc. 11th IEEE Symp. Logic in Computer Science (LICS 1996), New Brunswick, NJ, USA, July 1996, pp. 278–292. IEEE Comp. Soc. Press, Los Alamitos (1996)
Henzinger, Th.A., Nicollin, X., Sifakis, J., Yovine, S.: Symbolic model-checking for real-time systems. Information and Computation 111(2), 193–244 (1994)
Kesten, Y., Pnueli, A., Sifakis, J., Yovine, S.: Decidable integration graphs. Information and Computation 150(2), 209–243 (1999)
Koymans, R.: Specifying real-time properties with metric temporal logic. Real-Time Systems 2(4), 255–299 (1990)
Larsen, K.G., Pettersson, P., Yi, W.: Uppaal in a nutshell. Journal of Software Tools for Technology Transfer 1(1–2), 134–152 (1997)
Ouaknine, J., Worrell, J.: On the decidability of Metric Temporal Logic. In: Proc. 20th IEEE Symp. Logic in Computer Science (LICS 2005), Chicago, IL, USA, June 2005, pp. 188–197. IEEE Computer Society Press, Los Alamitos (2005)
Yovine, S.: Kronos: A verification tool for real-time systems. Journal of Software Tools for Technology Transfer 1(1–2), 123–133 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mokadem, H.B., Bérard, B., Bouyer, P., Laroussinie, F. (2006). Timed Temporal Logics for Abstracting Transient States. In: Graf, S., Zhang, W. (eds) Automated Technology for Verification and Analysis. ATVA 2006. Lecture Notes in Computer Science, vol 4218. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11901914_26
Download citation
DOI: https://doi.org/10.1007/11901914_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-47237-7
Online ISBN: 978-3-540-47238-4
eBook Packages: Computer ScienceComputer Science (R0)