Multi-head Monitoring of Metric Dynamic Logic
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Accepted author manuscript, 404 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | Automated Technology for Verification and Analysis - 18th International Symposium, ATVA 2020, Proceedings |
Editors | Dang Van Hung, Oleg Sokolsky |
Publisher | Springer |
Publication date | 2020 |
Pages | 233-250 |
ISBN (Print) | 9783030591519 |
DOIs | |
Publication status | Published - 2020 |
Event | 18th International Symposium on Automated Technology for Verification and Analysis, ATVA 2020 - Hanoi, Viet Nam Duration: 19 Oct 2020 → 23 Oct 2020 |
Conference
Conference | 18th International Symposium on Automated Technology for Verification and Analysis, ATVA 2020 |
---|---|
Land | Viet Nam |
By | Hanoi |
Periode | 19/10/2020 → 23/10/2020 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12302 LNCS |
ISSN | 0302-9743 |
ID: 258453436