Inferring lower bounds for runtime complexity

DOI10.4230/LIPICS.RTA.2015.334MaRDI QIDQ5277889zbMATH OpenOpenAlexFDO

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

Publication date 12 July 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.RTA.2015.334

zbMATH Keywords

inductionlower boundsruntime complexityterm rewriting

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds for runtime complexity of term rewriting
• Analyzing runtime complexity via innermost runtime complexity
• Complexity analysis for term rewriting by integer transition systems
• Transforming derivational complexity of term rewriting to runtime complexity
• Lower runtime bounds for integer programs

Cited in

(8)

• From Jinja bytecode to term rewriting: a complexity reflecting transformation
• Complexity analysis for term rewriting by integer transition systems
• Transforming derivational complexity of term rewriting to runtime complexity
• Analyzing program termination and complexity automatically with \textsf{AProVE}
• Lower bounds for runtime complexity of term rewriting
• Lower runtime bounds for integer programs
• Analyzing runtime complexity via innermost runtime complexity
• On lower bounds for the time of computation

Describes a project that uses

Uses Software

• AProVE

This page was built for publication: Inferring lower bounds for runtime complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277889)