Temporal Logic as Filtering.*

A. Rodionova, E. Bartocci, D. Nickovic, and R. Grosu.

We show that metric temporal logic (MTL) can be viewed as linear time-invariant filtering, by interpreting addition, multiplication, and their neutral elements, over the idempotent dioid (max,min,0,1). Moreover, by interpreting these operators over the field of reals (+,x,0,1), one can associate various quantitative semantics to a metric-temporal-logic formula, depending on the filter's kernel used: square, rounded-square, Gaussian, low-pass, band-pass, or high-pass. This remarkable connection between filtering and metric temporal logic allows us to freely navigate between the two, and to regard signal-feature detection as logical inference. To the best of our knowledge, this connection has not been established before. We prove that our qualitative, filtering semantics is identical to the classical MTL semantics. We also provide a quantitative semantics for MTL, which measures the normalized, maximum number of times a formula is satisfied within its associated kernel, by a given signal. We show that this semantics is sound, in the sense that, if its measure is 0, then the formula is not satisfied, and it is satisfied otherwise. We have implemented both of our semantics in Matlab, and illustrate their properties on various formulas and signals, by plotting their computed measures.

In Dependable Software Systems Engineering, Nato Science Series for Peace and Security, Vol. 50, pages 1-22, 2017, ISBN Print: 978-1-61499-809-9, ISBN Online: 978-1-61499-810-5.

* This work was partially supported by the AFOSR FA9550-14-1-0261, NSF-Frontiers Cyber-Physical Heart Award, FWF-NFN RiSE Award, FWF-DC LMCS Award, FFG Harmonia Award, FFG Em2Apps Award, and the TUW CPPS-DK Award.