Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations

DOI10.4230/LIPIcs.FSTTCS.2008.1762zbMath1248.68278OpenAlexW2169568716MaRDI QIDQ3165968

Andreas Schnabl, Johannes Waldmann, Georg Moser

Publication date: 19 October 2012

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

zbMATH Keywords

terminationterm rewritingautomationderivational complexity

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (12)

A combination framework for complexity ⋮ Unnamed Item ⋮ Uncurrying for termination and complexity ⋮ Analyzing Innermost Runtime Complexity Through Tuple Interpretations ⋮ A Perron-Frobenius theorem for deciding matrix growth ⋮ Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems ⋮ A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems ⋮ Applications and extensions of context-sensitive rewriting ⋮ Automatic Termination ⋮ The Derivational Complexity Induced by the Dependency Pair Method ⋮ Derivational complexity and context-sensitive Rewriting ⋮ Analyzing innermost runtime complexity of term rewriting by dependency pairs

Uses Software

• MiniSat

This page was built for publication: Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations