On Implementing Modular Complexity Analysis | Zendy

Harald Zankl | Zendy; Martin Korp | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On Implementing Modular Complexity Analysis

Author(s) -

Harald Zankl,

Martin Korp

Publication year - 2018

Publication title -

epic series in computing

Language(s) - English

Resource type - Conference proceedings

ISSN - 2398-7340

DOI - 10.29007/zm9s

Subject(s) - mathematical proof , modular design , computer science , upper and lower bounds , theoretical computer science , term (time) , computational complexity theory , algorithm , programming language , mathematics , mathematical analysis , physics , geometry , quantum mechanics

We recall the recent approach by (Zankl and Korp, 2010) to prove upper bounds on the (derivational) complexity of term rewrite systems modularly. In this note we show that this approach is suitable to tighten bounds after they have been established. The idea is to replace proof steps with a large bound by (new) proofs that yield smaller bounds. An evaluation of the approach shows the benets.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research