Optimistic and Pessimistic On-the-fly Analysis for Metric Temporal Graph Logic
- 23 June 2020
- book chapter
- Published by Springer Nature
- Vol. 12150, 276-294
Abstract
The nonpropositional Metric Temporal Graph Logic (MTGL) specifies the behavior of timed dynamic systems given by timed graph sequences (TGSs), which contain typed attributed graphs representing system states and the elapsed time between states. MTGL satisfaction can be analyzed for finite TGSs by translating its satisfaction problem to the satisfaction problem of nested graph conditions using a folding operation (aggregating a TGS into a graph with history) and a reduction operation (translating an MTGL condition into a nested graph condition). In this paper, we introduce an analysis procedure for MTGL to allow for an on-the-fly analysis of finite/infinite TGSs. To this end, we introduce a further (optimistic) reduction of MTGL conditions, which leads to violations during the on-the-fly analysis only when non-satisfaction is guaranteed in the future whereas the former (pessimistic) reduction leads to violations when satisfaction is not guaranteed in the future. We motivate the relevance of our analysis procedure, which uses both reduction operations, by means of a running example. Finally, we discuss prototypical support in the tool AutoGraph.Keywords
This publication has 21 references indexed in Scilit:
- k-Inductive Invariant Checking for Graph Transformation Systems2017
- Monitoring Metric First-Order Temporal PropertiesJournal of the ACM, 2015
- Modelling and analysis using GROOVEInternational Journal on Software Tools for Technology Transfer, 2011
- Symbolic graphs for attributed graph constraintsJournal of Symbolic Computation, 2011
- A brief account of runtime verificationThe Journal of Logic and Algebraic Programming, 2009
- Correctness of high-level transformation systems relative to nested conditionsMathematical Structures in Computer Science, 2009
- On Safe Service-Oriented Real-Time Coordination for Autonomous Vehicles2008
- Modeling and Verification of Cooperative Self-adaptive Mechatronic Systems2007
- Monitoring Temporal Properties of Continuous Signals2004
- Specifying real-time properties with metric temporal logicReal-Time Systems, 1990