David Cerna, Wolfgang Schreiner,
"Measuring the Gap: Algorithmic Approximation Bounds for the Space Complexity of Stream Specifications"
, Serie RISC Report Series, RISC, JKU, Hagenberg, Linz, 11-2016
Original Titel:
Measuring the Gap: Algorithmic Approximation Bounds for the Space Complexity of Stream Specifications
Sprache des Titels:
Englisch
Original Kurzfassung:
In previous work we presented an algorithmic procedure for analysing the space complexity of monitor specifications written in a fragment of predicate logic. These monitor specifications were developed for runtime monitoring of event streams. Our procedure provides accurate results for a large fragment of the possible specifications, but overestimates the space complexity of precisely those specifications which are more likely to be found in real world applications. Experiments hinted at a relationship between the extent our procedure over-approximates the space requirements of a specification and the quantifier structure of the specification. In this paper we provide a formalization of this relationship as approximation ratios, and are able to pinpoint ``good'' constructions, that is specifications using less memory. These results are first steps towards categorizing specifications based on memory efficiency. Notiz zur Publikation: submitted.