Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/86112| Title: | The cost of monitoring alone |
| Other Titles: | From Reactive Systems to Cyber-Physical Systems. Lecture Notes in Computer Science, vol 11500 |
| Authors: | Aceto, Luca Achilleos, Antonis Francalanza, Adrian Ingólfsdóttir, Anna Lehtinen, Karoliina |
| Keywords: | Computer software -- Verification Computer logic Object monitors (Computer software) |
| Issue Date: | 2019 |
| Publisher: | Springer Nature Switzerland AG |
| Citation: | Aceto, L., Achilleos, A., Francalanza, A., Ingólfsdóttir, A., & Lehtinen, K. (2019). The cost of monitoring alone. In: E. Bartocci, R. Cleaveland, R. Grosu, & O. Sokolsky (eds), From Reactive Systems to Cyber-Physical Systems. Lecture Notes in Computer Science, vol 11500 (pp. 259-275). Cham: Springer Nature Switzerland AG. |
| 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. |
| URI: | https://www.um.edu.mt/library/oar/handle/123456789/86112 |
| Appears in Collections: | Scholarly Works - FacICTCS |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| The Cost of Monitoring Alone.pdf Restricted Access | 571.6 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.