Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twenty-Second Annual IEEE Symposium on

Logic in Computer Science (LICS 2007)

Paper: The Cost of Punctuality (at LICS 2007)

Authors: Patricia Bouyer Nicolas Markey Joël Ouaknine James Worrell

Abstract

In an influential paper titled "The Benefits of Relaxing Punctuality" [2], Alur, Feder, and Henzinger introduced Metric Interval Temporal Logic (MITL) as a fragment of the real-time logic Metric Temporal Logic (MTL) in which exact or punctual timing constraints are banned. Their main result showed that model checking and satisfiability for MITL are both EXPSPACE-Complete. Until recently, it was widely believed that admitting even the simplest punctual specifications in any linear-time temporal logic would automatically lead to undecidability. Although this was recently disproved, until now no punctual fragment of MTL was known to have even primitive recursive complexity (with certain decidable fragments having provably non-primitive recursive complexity). In this paper we identify a ‘co-flat’ subset of MTL that is capable of expressing a large class of punctual specifications and for which model checking (although not satisfiability) has no complexity cost over MITL. Our logic is moreover qualitatively different from MITL in that it can express properties that are not timed-regular. Correspondingly, our decision procedures do not involve translating formulas into finite-state automata, but rather into certain kinds of reversal-bounded Turing machines. Using this translation we show that the model checking problem for our logic is EXPSPACE-Complete

BibTeX

  @InProceedings{BouyerMarkeyOuaknin-TheCostofPunctualit,
    author = 	 {Patricia Bouyer and Nicolas Markey and Joël Ouaknine and James Worrell},
    title = 	 {The Cost of Punctuality},
    booktitle =  {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)},
    year =	 {2007},
    month =	 {July}, 
    pages =      {109--118},
    location =   {Wroclaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski