The cost of monitoring alone

Luca Aceto; Antonis Achilleos; Adrian Francalanza; Anna Ingólfsdóttir; Karoliina Lehtinen

doi:10.1007/978-3-030-31514-6_15

The cost of monitoring alone

Luca Aceto, Antonis Achilleos^*, Adrian Francalanza, Anna Ingólfsdóttir, Karoliina Lehtinen

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

2 Citations (Scopus)

Abstract

We compare the succinctness of two monitoring systems for properties of infinite traces, namely parallel and regular monitors. Although a parallel monitor can be turned into an equivalent regular monitor, the cost of this transformation is a double-exponential blowup in the syntactic size of the monitors, and a triple-exponential blowup when the goal is a deterministic monitor. We show that these bounds are tight and that they also hold for translations between corresponding fragments of Hennessy-Milner logic with recursion over infinite traces.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer-Verlag
Pages	259-275
Number of pages	17
DOIs	https://doi.org/10.1007/978-3-030-31514-6_15
Publication status	Published - 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11500 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Bibliographical note

Funding Information:
This research was partially supported by the projects “TheoFoMon: Theoretical Foundations for Monitorability” (grant number: 163406-051) and “Epistemic Logic for Distributed Runtime Monitoring” (grant number: 184940-051) of the Icelandic Research Fund, by the BMBF project “Aramis II” (project number: 01IS160253) and the EPSRC project “Solving parity games in theory and practice” (project number: EP/P020909/1).

Publisher Copyright:
© Springer Nature Switzerland AG 2019.

Other keywords

Determinization
Hennessy Milner logic with recursion
Logical fragments
Monitors
Runtime Verification
State complexity

Access to Document

10.1007/978-3-030-31514-6_15

Cite this

Aceto, L., Achilleos, A., Francalanza, A., Ingólfsdóttir, A., & Lehtinen, K. (2019). The cost of monitoring alone. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 259-275). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11500 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-030-31514-6_15

Aceto, Luca ; Achilleos, Antonis ; Francalanza, Adrian et al. / The cost of monitoring alone. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer-Verlag, 2019. pp. 259-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{d55d1e52caa84b539900acbe40d3cf7d,

title = "The cost of monitoring alone",

abstract = "We compare the succinctness of two monitoring systems for properties of infinite traces, namely parallel and regular monitors. Although a parallel monitor can be turned into an equivalent regular monitor, the cost of this transformation is a double-exponential blowup in the syntactic size of the monitors, and a triple-exponential blowup when the goal is a deterministic monitor. We show that these bounds are tight and that they also hold for translations between corresponding fragments of Hennessy-Milner logic with recursion over infinite traces.",

keywords = "Determinization, Hennessy Milner logic with recursion, Logical fragments, Monitors, Runtime Verification, State complexity",

author = "Luca Aceto and Antonis Achilleos and Adrian Francalanza and Anna Ing{\'o}lfsd{\'o}ttir and Karoliina Lehtinen",

note = "Funding Information: This research was partially supported by the projects “TheoFoMon: Theoretical Foundations for Monitorability” (grant number: 163406-051) and “Epistemic Logic for Distributed Runtime Monitoring” (grant number: 184940-051) of the Icelandic Research Fund, by the BMBF project “Aramis II” (project number: 01IS160253) and the EPSRC project “Solving parity games in theory and practice” (project number: EP/P020909/1). Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.",

year = "2019",

doi = "10.1007/978-3-030-31514-6_15",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "259--275",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

Aceto, L, Achilleos, A, Francalanza, A, Ingólfsdóttir, A & Lehtinen, K 2019, The cost of monitoring alone. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11500 LNCS, Springer-Verlag, pp. 259-275. https://doi.org/10.1007/978-3-030-31514-6_15

The cost of monitoring alone. / Aceto, Luca; Achilleos, Antonis; Francalanza, Adrian et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer-Verlag, 2019. p. 259-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11500 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - The cost of monitoring alone

AU - Aceto, Luca

AU - Achilleos, Antonis

AU - Francalanza, Adrian

AU - Ingólfsdóttir, Anna

AU - Lehtinen, Karoliina

N1 - Funding Information: This research was partially supported by the projects “TheoFoMon: Theoretical Foundations for Monitorability” (grant number: 163406-051) and “Epistemic Logic for Distributed Runtime Monitoring” (grant number: 184940-051) of the Icelandic Research Fund, by the BMBF project “Aramis II” (project number: 01IS160253) and the EPSRC project “Solving parity games in theory and practice” (project number: EP/P020909/1). Publisher Copyright: © Springer Nature Switzerland AG 2019.

PY - 2019

Y1 - 2019

N2 - We compare the succinctness of two monitoring systems for properties of infinite traces, namely parallel and regular monitors. Although a parallel monitor can be turned into an equivalent regular monitor, the cost of this transformation is a double-exponential blowup in the syntactic size of the monitors, and a triple-exponential blowup when the goal is a deterministic monitor. We show that these bounds are tight and that they also hold for translations between corresponding fragments of Hennessy-Milner logic with recursion over infinite traces.

AB - We compare the succinctness of two monitoring systems for properties of infinite traces, namely parallel and regular monitors. Although a parallel monitor can be turned into an equivalent regular monitor, the cost of this transformation is a double-exponential blowup in the syntactic size of the monitors, and a triple-exponential blowup when the goal is a deterministic monitor. We show that these bounds are tight and that they also hold for translations between corresponding fragments of Hennessy-Milner logic with recursion over infinite traces.

KW - Determinization

KW - Hennessy Milner logic with recursion

KW - Logical fragments

KW - Monitors

KW - Runtime Verification

KW - State complexity

UR - http://www.scopus.com/inward/record.url?scp=85073151351&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-31514-6_15

DO - 10.1007/978-3-030-31514-6_15

M3 - Chapter

AN - SCOPUS:85073151351

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 259

EP - 275

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer-Verlag

ER -

Aceto L, Achilleos A, Francalanza A, Ingólfsdóttir A, Lehtinen K. The cost of monitoring alone. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer-Verlag. 2019. p. 259-275. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-31514-6_15

The cost of monitoring alone

Abstract

Publication series

Bibliographical note

Other keywords

Access to Document

Fingerprint

Cite this