As Time Goes By II
Thom Frühwirth · Electronic Notes in Theoretical Computer Science · 2002
In previous papers we showed that from a suitable termination order (called ranking) one can automatically compute the worst-case time complexity of a CHR constraint simplification rule program from its program text. We combined the worst-case derivation length of a query predicted from its ranking with a worst-case estimate of the number and cost of rule application attempts and the cost of rule applications to obtain the desired meta-theorem. Here we generalize the approach presented in these papers and use it to analyse several non-trivial rule-based constraint solver programs. These results also hold for naive CHR implementations. We also present empirical evidence through test runs that the actual run-time of a state-of-the-art CHR implementation is much better due to optimizations like indexing.