Multi-head Monitoring of Metric Dynamic Logic

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Accepteret manuskript, 404 KB, PDF-dokument

We develop a monitoring algorithm for metric dynamic logic, an extension of metric temporal logic with regular expressions. The monitor computes whether a given formula is satisfied at every position in an input trace of time-stamped events. Our monitor follows the multi-head paradigm: it reads the input simultaneously at multiple positions and moves its reading heads asynchronously. This mode of operation results in unprecedented space complexity guarantees for metric dynamic logic: The monitor’s memory consumption neither depends on the event-rate, i.e., the number of events within a fixed time-unit, nor on the numeric constants occurring in the quantitative temporal constraints in the given formula. We formally prove our algorithm correct in the Isabelle proof assistant, integrate it in the Hydra monitoring tool, and empirically demonstrate its strong performance.

OriginalsprogEngelsk
TitelAutomated Technology for Verification and Analysis - 18th International Symposium, ATVA 2020, Proceedings
RedaktørerDang Van Hung, Oleg Sokolsky
ForlagSpringer
Publikationsdato2020
Sider233-250
ISBN (Trykt)9783030591519
DOI
StatusUdgivet - 2020
Begivenhed18th International Symposium on Automated Technology for Verification and Analysis, ATVA 2020 - Hanoi, Vietnam
Varighed: 19 okt. 202023 okt. 2020

Konference

Konference18th International Symposium on Automated Technology for Verification and Analysis, ATVA 2020
LandVietnam
ByHanoi
Periode19/10/202023/10/2020
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind12302 LNCS
ISSN0302-9743

ID: 258453436