Almost Event-Rate Independent Monitoring of Metric Dynamic Logic

David Basin, Srđan Krstić, Dmitriy Traytel

Abstract

Linear temporal logic(LTL) and its quantitative extension metric temporal logic (MTL) are standard languages for specifying system behaviors. Regular expressions are an even more expressive formalism in the non-metric setting and several extensions of LTL, including the recently proposed linear dynamic logic (LDL), offer regular-expression-like constructs. We extend LDL with past operators and quantitative features. The resulting metric dynamic logic (MDL) offers the quantitative temporal conveniences of MTL while increasing its expressiveness. We develop and evaluate an online monitoring algorithm for MDL whose space-consumption is almost event-rate independent—a notion that characterizes monitors that scale to high-velocity event streams.

Paper draft