An Algorithmic Approach to Bounding the Time Complexity of Stream Specifications

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.