liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Observation Strategies for Event Detection with Incidence on Runtime Verification: Theory, Algorithms, Experimentation
Dept. of Computer Science, Nova Universidade de Lisboa, Lisbon.
Linköping University, Department of Science and Technology, Media and Information Technology. Linköping University, The Institute of Technology.
Dept. of Computer Science, Nova Universidade de Lisboa, Lisbon.
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
Abstract [en]

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.
Keyword [en]
Event detection – Runtime verification – Temporal logic – Logic programming – Complexity
National Category
Computer and Information Science
URN: urn:nbn:se:liu:diva-73061DOI: 10.1007/s10472-011-9259-5ISI: 000300019900002OAI: diva2:465613
Available from: 2011-12-14 Created: 2011-12-14 Last updated: 2012-03-02

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Dell'Acqua, Pierangelo
By organisation
Media and Information TechnologyThe Institute of Technology
In the same journal
Annals of Mathematics and Artificial Intelligence
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 93 hits
ReferencesLink to record
Permanent link

Direct link