Observation Strategies for Event Detection with Incidence on Runtime Verification: Theory, Algorithms, Experimentation
2011 (English)In: Annals of Mathematics and Artificial Intelligence, ISSN 1012-2443, E-ISSN 1573-7470, Vol. 62, no 3-4, 161-186 p.Article in journal (Refereed) Published
Many applications (such as system and user monitoring, runtime verification, diagnosis, observation-based decision making, intention recognition) all require to detect the occurrence of an event in a system, which entails the ability to observe the system. Observation can be costly, so it makes sense to try and reduce the number of observations, without losing full certainty about the event’s actual occurrence. In this paper, we propose a formalization of this problem. We formally show that, whenever the event to be detected follows a discrete spatial or temporal pattern, then it is possible to reduce the number of observations. We discuss exact and approximate algorithms to solve the problem, and provide an experimental evaluation of them. We apply the resulting algorithms to verification of linear temporal logics formulæ. Finally, we discuss possible generalizations and extensions, and, in particular, how event detection can benefit from logic programming techniques.
Place, publisher, year, edition, pages
Springer, 2011. Vol. 62, no 3-4, 161-186 p.
Event detection – Runtime verification – Temporal logic – Logic programming – Complexity
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-73061DOI: 10.1007/s10472-011-9259-5ISI: 000300019900002OAI: oai:DiVA.org:liu-73061DiVA: diva2:465613