Modular Complexity Analysis via Relative Complexity

DOI10.4230/LIPIcs.RTA.2010.385zbMath1236.68158OpenAlexW1517466677MaRDI QIDQ5389157

Harald Zankl, Martin Korp

Publication date: 25 April 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_6a0e.html

zbMATH Keywords

term rewritingcomplexity analysisderivation lengthrelative complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items (9)

A combination framework for complexity ⋮ From Jinja bytecode to term rewriting: a complexity reflecting transformation ⋮ Uncurrying for termination and complexity ⋮ Modularity in term rewriting revisited ⋮ Decreasing diagrams and relative termination ⋮ Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems ⋮ A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems ⋮ A new order-theoretic characterisation of the polytime computable functions ⋮ Analyzing innermost runtime complexity of term rewriting by dependency pairs

Uses Software

• MiniSat
• Tyrolean

This page was built for publication: Modular Complexity Analysis via Relative Complexity