Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Session 9. Time

Allen Linear (Interval) Temporal Logic – Translation to LTL and Monitor Synthesis

Grigore Roşu1 and Saddek Bensalem2

(1)  Department of Computer Science, University of Illinois at Urbana-Champaign, USA
(2)  VERIMAG, 2 Avenue de Vignate, 38610 Gieres, France
Abstract
The relationship between two well established formalisms for temporal reasoning is first investigated, namely between Allen’s interval algebra (or Allen’s temporal logic, abbreviated $\textsf{ATL}$ ) and linear temporal logic ( $\textsf{LTL}$ ). A discrete variant of $\textsf{ATL}$ is defined, called Allen linear temporal logic ( $\textsf{ALTL}$ ), whose models are ω-sequences of timepoints. It is shown that any $\textsf{ALTL}$ formula can be linearly translated into an equivalent $\textsf{LTL}$ formula, thus enabling the use of $\textsf{LTL}$ techniques on $\textsf{ALTL}$ requirements. This translation also implies the NP-completeness of $\textsf{ATL}$ satisfiability. Then the problem of monitoring $\textsf{ALTL}$ requirements is investigated, showing that it reduces to checking satisfiability; the similar problem for unrestricted $\textsf{LTL}$ is known to require exponential space. An effective monitoring algorithm for $\textsf{ALTL}$ is given, which has been implemented and experimented with in the context of planning applications.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.111 • Server: mpweb20
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)