@techreport{RISC5403,author = {David M. Cerna and Wolfgang Schreiner},
title = {{An Algorithmic Approach to Bounding the Time Complexity of Stream Specifications}},
language = {english},
abstract = {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.},
year = {2017},
month = {January },
howpublished = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University, Linz, Austria},
length = {12},
type = {Technical Report},
type = {RISC Report Series},
institution = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz},
address = {Altenberger Straße 69, 4040 Linz, Austria},
issn = {2791-4267 (online)}
}