Nicolas Markey

Résumé

We consider quantitative model checking in durational Kripke structures (Kripke structures where transitions have integer durations) with timed temporal logics where subscripts put quantitative constraints on the time it takes before a property is satisfied. We investigate the conditions that allow polynomial-time model checking algorithms for timed versions of CTL and exhibit an important gap between logics where subscripts of the form "= c" (exact duration) are allowed, and simpler logics that only allow subscripts of the form "≤ c" or "≥ c" (bounded duration).

A surprising outcome of this study is that it provides the second example of a Δ2P-complete model checking problem.

@inproceedings{fossacs2002-LMS,
  author =              {Laroussinie, Fran{\c c}ois and Markey, Nicolas and
                         Schnoebelen, {\relax Ph}ilippe},
  title =               {On Model Checking Durational {K}ripke Structures
                         (Extended Abstract)},
  editor =              {Nielsen, Mogens and Engberg, Uffe},
  booktitle =           {{P}roceedings of the 5th {I}nternational
                         {C}onference on {F}oundations of {S}oftware
                         {S}cience and {C}omputation {S}tructure
                         ({FoSSaCS}'02)},
  acronym =             {{FoSSaCS}'02},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {2303},
  pages =               {264-279},
  year =                {2002},
  month =               apr,
  doi =                 {10.1007/3-540-45931-6_19},
  abstract =            {We consider quantitative model checking in
                         \emph{durational Kripke structures} (Kripke
                         structures where transitions have integer durations)
                         with timed temporal logics where subscripts put
                         quantitative constraints on the time it takes before
                         a property is satisfied. We investigate the
                         conditions that allow polynomial-time model checking
                         algorithms for timed versions of CTL and exhibit an
                         important gap between logics where subscripts of the
                         form {"}\(= c\){"} (exact duration) are allowed, and
                         simpler logics that only allow subscripts of the
                         form {"}\(\leq c\){"} or {"}\(\geq c\){"} (bounded
                         duration).\par A surprising outcome of this study is
                         that it provides the second example of a
                         \(\Delta_2^P\)-complete model checking problem.},
}