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
Ingolfsdottir, 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 SizeFormat 
deter-mon-2017.pdf424.78 kBAdobe PDFView/Open


Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.