As Time Goes By II: More Automatic Complexity Analysis of Concurrent Rule Programs
✍ Scribed by Thom Frühwirth
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 339 KB
- Volume
- 59
- Category
- Article
- ISSN
- 1571-0661
No coin nor oath required. For personal study only.
✦ Synopsis
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 (\mathrm{CHR}) implementation is much better due to optimizations like indexing.