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 formulae. Finally, we discuss possible generalizations and extensions, and, in particular, how event detection can benefit from logic programming techniques.

Observation strategies for event detection with incidence on runtime verification: theory, algorithms, experimentation

ALBERTI, Marco
Primo
;
2011

Abstract

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 formulae. Finally, we discuss possible generalizations and extensions, and, in particular, how event detection can benefit from logic programming techniques.
2011
Alberti, Marco; P., Dell'Acqua; L. M., Pereira
File in questo prodotto:
File Dimensione Formato  
runtime_verification_amai.pdf

accesso aperto

Descrizione: Pre-print
Tipologia: Pre-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 501.62 kB
Formato Adobe PDF
501.62 kB Adobe PDF Visualizza/Apri
Alberti2011_Article_ObservationStrategiesForEventD.pdf

solo gestori archivio

Descrizione: Full text editoriale
Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 585.09 kB
Formato Adobe PDF
585.09 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/1871928
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact