Quantitative Robustness for Signal Temporal Logic With Time-Freeze Quantifiers
- 6 June 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 42 (12) , 4436-4449
Abstract
Signal temporal logic (STL) is a variant of metric temporal logic (MTL) which can express intricate temporal requirements over signals and has found wide adoption for expressing requirements over complex control systems models. A key factor in the success of STL has been that of quantitative robustness, and the development of efficient algorithms for computing the robustness values over traces. The real-valued quantitative robustness of a signal with respect to an STL property quantifies the degree of satisfaction or violation of the property by the signal. In this work, we introduce a notion of robustness for a more expressive logic, timed STL (TSTL), which can be seen as timed propositional temporal logic (TPTL) with predicates defined over real-valued signals. This logic can express many natural engineering requirements that STL cannot. We also develop algorithms for computing this robustness value over traces in the pointwise semantics. While the robustness computation for general TSTL formulas is PSPACE-hard due to the PSPACE-hardness of the monitoring problem for TPTL, for the special case of one variable TSTL, a fragment of TSTL which is still more expressive than STL, we develop an optimized algorithm which computes robustness in time linear in the length of the trace. Finally, we experimentally validate the tractability of our algorithms with our prototype tool in MATLAB.Keywords
Funding Information
- National Science Foundation (2240126)
This publication has 38 references indexed in Scilit:
- Quantitative reactive modeling and verificationComputer Science - Research and Development, 2013
- Efficient Robust Monitoring for STL2013
- Monitoring properties of analog and mixed-signal circuitsInternational Journal on Software Tools for Technology Transfer, 2012
- Quantitative languagesACM Transactions on Computational Logic, 2010
- On the expressiveness of TPTL and MTLInformation and Computation, 2010
- Robustness of temporal logic specifications for continuous-time signalsTheoretical Computer Science, 2009
- Expressiveness of Metric modalities for continuous timeLogical Methods in Computer Science, 2007
- Model checking restricted sets of timed pathsTheoretical Computer Science, 2006
- A theory of timed automataTheoretical Computer Science, 1994
- A really temporal logicJournal of the ACM, 1994