Inferring Lower Bounds for Runtime Complexity Article Swipe

View

Related Concepts

Complement (music) Computer science Sequence (biology) Upper and lower bounds Key (lock) Theoretical computer science Term (time) Relation (database) Computational complexity theory Algorithm Mathematics Data mining Biology Genetics Complementation Chemistry Phenotype Physics Computer security Biochemistry Gene Quantum mechanics Mathematical analysis

Florian Frohn , Jürgen Giesl , Jera Hensel , Cornelius Aschermann , Thomas Ströder ·

YOU? · · 2015 · Open Access · · DOI: https://doi.org/10.4230/lipics.rta.2015.334 · OA: W2296265259

We present the first approach to deduce lower bounds for innermost runtime complexity of term rewrite systems (TRSs) automatically. Inferring lower runtime bounds is useful to detect bugs and to complement existing techniques that compute upper complexity bounds. The key idea of our approach is to generate suitable families of rewrite sequences of a TRS and to find a relation between the length of such a rewrite sequence and the size of the first term in the sequence. We implemented our approach in the tool AProVE and evaluated it by extensive experiments.