Abstract
We extend the framework of ATL model-checking to “simply timed” concurrent game structures, i.e., multi-agent structures where each transition carry an integral duration (or interval thereof). While the case of single durations is easily handled from the semantics point of view, intervals of durations raise several interesting questions. Moreover subtle algorithmic problems have to be handled when dealing with model checking. We propose a semantics for which we develop efficient (PTIME) algorithms for timed ATL without equality constraints, while the general case is shown to be EXPTIME-complete.
This work is partly supported by ACI Sécurité & Informatique CORTOS, a program of the French ministry of research.
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.L.: Model-checking in dense real-time. Information & Computation 104(1), 2–34 (1993)
Alur, R., Dill, D.L.: A theory of timed automata. Theoretical Computer Science 126(2), 183–235 (1994)
Alur, R., Henzinger, T.A.: Modularity for timed and hybrid systems. In: Mazurkiewicz, A., Winkowski, J. (eds.) CONCUR 1997. LNCS, vol. 1243, pp. 74–88. Springer, Heidelberg (1997)
Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. In: Proc 38th Annual Symp. on Foundations of Computer Science (FOCS 1997), pp. 100–109. IEEE Comp. Soc. Press, Los Alamitos (1997)
Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM 49(5), 672–713 (2002)
Asarin, E., Maler, O., Pnueli, A., Sifakis, J.: Controller synthesis for timed automata. In: Proc IFAC Symp. on System Structure and Control. Elsevier, Amsterdam (1998)
Bérard, B., Bidoit, M., Finkel, A., Laroussinie, F., Petit, A., Petrucci, L., Schnoebelen, P.: Systems and Software Verification. Model-Checking Techniques and Tools. Springer, Heidelberg (2001)
Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys 24(3), 293–318 (1992)
Campos, S., Clarke, E.M.: Real-time symbolic model checking for discrete time models. In: Theories and Experiences for Real-Time System Development. AMAST Series in Computing, vol. 2, pp. 129–145. World Scientific, Singapore (1995)
Cassez, F., David, A., Fleury, E., Larsen, K.G., Lime, D.: Efficient on-the-fly algorithms for the analysis of timed games. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 66–80. Springer, Heidelberg (2005)
Clarke, E.M., Emerson, E.A.: Design and synthesis of synchronization skeletons using branching time temporal logic. In: Kozen, D. (ed.) Logic of Programs 1981. LNCS, vol. 131, pp. 52–71. Springer, Heidelberg (1982)
Clarke, E.M., Grumberg, O., Peled, D.A.: Model Checking. MIT Press, Cambridge (1999)
de Alfaro, L., Faella, M., Henzinger, T.A., Majumdar, R., Stoelinga, M.: The element of surprise in timed games. In: Amadio, R.M., Lugiez, D. (eds.) CONCUR 2003. LNCS, vol. 2761, pp. 142–156. Springer, Heidelberg (2003)
Emerson, E.A., Mok, A.K.-L., Sistla, A.P., Srinivasan, J.: Quantitative temporal reasoning. Real-Time Systems 4, 331–352 (1992)
Jurdziński, M.: Countdown games. Personal communication (March 2006)
Laroussinie, F., Markey, N., Oreiby, G.: Expressiveness and complexity of ATL. Research Report LSV-06-03, Laboratoire Spécification et Vérification, ENS Cachan, France (February 2006)
Laroussinie, F., Markey, N., Schnoebelen, P.: Efficient timed model checking for discrete-time systems. Theoretical Computer Science 353(1-3), 249–271 (2006)
Maler, O., Pnueli, A., Sifakis, J.: On the synthesis of discrete controllers for timed systems. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol. 900, pp. 229–242. Springer, Heidelberg (1995)
Markey, N., Schnoebelen, P.: Symbolic model checking of simply-timed systems. In: Lakhnech, Y., Yovine, S. (eds.) FORMATS 2004 and FTRTFT 2004. LNCS, vol. 3253, pp. 102–117. Springer, Heidelberg (2004)
McMillan, K.L.: Symbolic Model Checking: An Approach to the State Explosion Problem. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA (1992)
Pnueli, A.: The temporal logic of programs. In: Proc. 18th IEEE Symp. Foundations of Computer Science (FOCS 1977), pp. 46–57. IEEE Comp. Soc. Press, Los Alamitos (1977)
Queille, J.-P., Sifakis, J.: Specification and verification of concurrent systems in CESAR. In: Dezani-Ciancaglini, M., Montanari, U. (eds.) Programming 1982. LNCS, vol. 137, pp. 337–351. Springer, Heidelberg (1982)
Ramadge, P.J., Wonham, W.M.: The control of discrete event systems. Proceedings of the IEEE 77(1), 81–98 (1989)
Schobbens, P.-Y., Bontemps, Y.: Real-time concurrent game structures. Personal communication (December 2005)
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
Laroussinie, F., Markey, N., Oreiby, G. (2006). Model-Checking Timed ATL for Durational Concurrent Game Structures. In: Asarin, E., Bouyer, P. (eds) Formal Modeling and Analysis of Timed Systems. FORMATS 2006. Lecture Notes in Computer Science, vol 4202. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11867340_18
Download citation
DOI: https://doi.org/10.1007/11867340_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45026-9
Online ISBN: 978-3-540-45031-3
eBook Packages: Computer ScienceComputer Science (R0)