RISC JKU
  • @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)}
    }