@inproceedings{f19455610128483db61be94f31302757,
title = "Automatic complexity analysis",
abstract = "We consider the problem of automating the derivation oftight asymptotic complexity bounds for solving Horn clauses. Clearly,the solving time crucially depends on the “sparseness” of the computed relations. Therefore, our asymptotic runtime analysis is accompanied byan asymptotic sparsity calculus together with an asymptotic sparsity analysis. The technical problem here is that least fixpoint iteration failson asymptotic complexity expressions: the intuitive reason is that O(1)+O(1) = O(1) but O(1) + · · · + O(1) may return any value.",
keywords = "Automatic complexity analysis, Horn clauses, Program analysis, Sparseness",
author = "Flemming Nielson and Nielson, {Hanne Riis} and Helmut Seidl",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 11th European Symposium on Programming, ESOP 2002 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002 ; Conference date: 08-04-2002 Through 12-04-2002",
year = "2002",
doi = "10.1007/3-540-45927-8_18",
language = "English",
isbn = "3540433635",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "243--261",
editor = "{Le M{\'e}tayer}, Daniel",
booktitle = "Programming Languages and Systems - 11th European Symposium on Programming, ESOP 2002 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002, Proceedings",
}