Transforming derivational complexity of term rewriting to runtime complexity

DOI10.1007/978-3-030-29007-8_20MaRDI QIDQ2180239zbMATH OpenOpenAlexFDO

Authors Carsten Fuhs

Publication date 13 May 2020

Full work available at URL https://eprints.bbk.ac.uk/id/eprint/28185/1/FroCoS19-rcdc.pdf

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Recommendations

• Complexity analysis for term rewriting by integer transition systems
• Modular complexity analysis for term rewriting
• Lower bounds for runtime complexity of term rewriting
• Modular complexity analysis via relative complexity
• Inferring lower bounds for runtime complexity

Cited in

(11)

• The exact hardness of deciding derivational and runtime complexity
• scientific article; zbMATH DE number 5788680 (Why is no real title available?)
• Derivational complexity is an invariant cost model
• Analysing parallel complexity of term rewriting
• Inferring lower bounds for runtime complexity
• Lower bounds for runtime complexity of term rewriting
• Complexity analysis for term rewriting by integer transition systems
• Applications and extensions of context-sensitive rewriting
• From innermost to full almost-sure termination of probabilistic term rewriting
• From Jinja bytecode to term rewriting: a complexity reflecting transformation
• Trace rewriting: Computing normal forms in time O(n log n)

Describes a project that uses

Uses Software

• AProVE

This page was built for publication: Transforming derivational complexity of term rewriting to runtime complexity

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