On the quantitative semantics of regular expressions over real-valued signals
15th International Conference on Formal Modelling and Analysis of Timed Systems, FORMATS 2017, Berlin, Almanya, 5 - 07 Eylül 2017, cilt.10419 LNCS, ss.189-206, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Cilt numarası: 10419 LNCS
- Doi Numarası: 10.1007/978-3-319-65765-3_11
- Basıldığı Şehir: Berlin
- Basıldığı Ülke: Almanya
- Sayfa Sayıları: ss.189-206
- Boğaziçi Üniversitesi Adresli: Hayır
Özet
Signal regular expressions can specify sequential properties of real-valued signals based on threshold conditions, regular operations, and duration constraints. In this paper we endow them with a quantitative semantics which indicates how robustly a signal matches or does not match a given expression. First, we show that this semantics is a safe approximation of a distance between the signal and the language defined by the expression. Then, we consider the robust matching problem, that is, computing the quantitative semantics of every segment of a given signal relative to an expression. We present an algorithm that solves this problem for piecewise-constant and piecewise-linear signals and show that for such signals the robustness map is a piecewise-linear function. The availability of an indicator describing how robustly a signal segment matches some regular pattern provides a general framework for quantitative monitoring of cyber-physical systems.