David Cerna, Wolfgang Schreiner,
"An Algorithmic Approach to Bounding the Time Complexity of Stream Specifications"
, Serie RISC Report Series, Johannes Kepler University Linz, Austria, RISC, JKU, Hagenberg, Linz, 1-2017
An Algorithmic Approach to Bounding the Time Complexity of Stream Specifications
Sprache des Titels:
In previous work an algorithmic procedure for analysing the space complexity of monitor speci- fications, written in a fragment of predicate logic, was presented. These monitor specifications were developed for the runtime monitoring of event streams. The algorithm provides accurate results for a large fragment of the possible specifications and can be easily extended to all specifications. In this work we follow the same approach, using the same theoretical foundations, to develop a algorithm computing the time complexity of our monitor specifications. In our previous work, the measure for space complexity was the monitor?s runtime representation size, i.e. the number of instances in memory during checking of the specification. In this work we consider the number of quantifier variable value assignments as the measurement of time complexity. The result is an algorithm which gives precise results for the entire core specification language.
Sprache der Kurzfassung:
RISC Report Series, Johannes Kepler University Linz, Austria