Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/23173| Title: | On the complexity of determinizing monitors |
| Authors: | Aceto, Luca Achilleos, Antonis Francalanza, Adrian Ingólfsdóttir, Anna Kjartansson, Saevar Orn |
| Keywords: | Autonomous distributed systems Computer network architectures Computer software -- Development Formal methods (Computer science) Computer software -- Verification Aspect-oriented programming |
| Issue Date: | 2017 |
| Publisher: | Springer |
| Citation: | Aceto, L., Achilleos, A., Francalanza, A., Ingólfsdóttir, A., & Kjartansson, S. Ö. (2017). On the complexity of determinizing monitors. On the complexity of determinizing monitors, Marne-la-Vallée. 1-12. |
| Abstract: | We examine the determinization of monitors. We demonstrate that every monitor is equivalent to a deterministic one, which is at most doubly exponential in size with respect to the original monitor. When monitors are described as CCS-like processes, this doubly-exponential bound is optimal. When (deterministic) monitors are described as finite automata (as their LTS), then they can be exponentially more succinct than their CCS process form. |
| URI: | https://www.um.edu.mt/library/oar//handle/123456789/23173 |
| Appears in Collections: | Scholarly Works - FacICTCS |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| deter-mon-2017.pdf | 424.78 kB | Adobe PDF | View/Open |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.