Online quantitative timed pattern matching with semiring-valued weighted automata
M Waga - Formal Modeling and Analysis of Timed Systems: 17th …, 2019 - Springer
Formal Modeling and Analysis of Timed Systems: 17th International Conference …, 2019•Springer
Monitoring of a signal plays an essential role in the runtime verification of cyber-physical
systems. Qualitative timed pattern matching is one of the mathematical formulations of
monitoring, which gives a Boolean verdict for each sub-signal according to the satisfaction of
the given specification. There are two orthogonal directions of extension of the qualitative
timed pattern matching. One direction on the result is quantitative: what engineers want is
often not a qualitative verdict but the quantitative measurement of the satisfaction of the …
systems. Qualitative timed pattern matching is one of the mathematical formulations of
monitoring, which gives a Boolean verdict for each sub-signal according to the satisfaction of
the given specification. There are two orthogonal directions of extension of the qualitative
timed pattern matching. One direction on the result is quantitative: what engineers want is
often not a qualitative verdict but the quantitative measurement of the satisfaction of the …
Abstract
Monitoring of a signal plays an essential role in the runtime verification of cyber-physical systems. Qualitative timed pattern matching is one of the mathematical formulations of monitoring, which gives a Boolean verdict for each sub-signal according to the satisfaction of the given specification. There are two orthogonal directions of extension of the qualitative timed pattern matching. One direction on the result is quantitative: what engineers want is often not a qualitative verdict but the quantitative measurement of the satisfaction of the specification. The other direction on the algorithm is online checking: the monitor returns some verdicts before obtaining the entire signal, which enables to monitor a running system. It is desired from application viewpoints. In this paper, we conduct these two extensions, taking an automata-based approach. This is the first quantitative and online timed pattern matching algorithm to the best of our knowledge. More specifically, we employ what we call timed symbolic weighted automata to specify quantitative specifications to be monitored, and we obtain an online algorithm using the shortest distance of a weighted variant of the zone graph and dynamic programming. Moreover, our problem setting is semiring-based and therefore, general. Our experimental results confirm the scalability of our algorithm for specifications with a time-bound.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果