Transforming derivational complexity of term rewriting to runtime complexity

DOI10.1007/978-3-030-29007-8_20zbMATH Open1435.68132OpenAlexW2969639005MaRDI QIDQ2180239FDOQ2180239

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

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

Mathematics Subject Classification ID

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

Cited In (11)

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

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)