Revisiting matrix interpretations for polynomial derivational complexity of term rewriting

DOI10.1007/978-3-642-16242-8_39MaRDI QIDQ4933331zbMATH OpenOpenAlexFDO

Authors Friedrich Neurauter, Harald Zankl, Aart Middeldorp

Publication date 12 October 2010

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16242-8_39

zbMATH Keywords

derivational complexitypolynomial matrix interpretations

Mathematics Subject Classification ID

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

Recommendations

• Polynomially bounded matrix interpretations
• Complexity analysis of term rewriting based on matrix and context dependent interpretations
• Joint spectral radius theory for automated complexity analysis of rewrite systems
• Matrix interpretations on polyhedral domains
• From Matrix Interpretations over the Rationals to Matrix Interpretations over the Naturals

Cited in

(11)

• Polynomially bounded matrix interpretations
• Joint spectral radius theory for automated complexity analysis of rewrite systems
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• Complexity analysis of term rewriting based on matrix and context dependent interpretations
• Derivational complexity and context-sensitive Rewriting
• Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
• Matrix interpretations on polyhedral domains
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Uncurrying for termination and complexity
• Applications and extensions of context-sensitive rewriting
• A Perron-Frobenius theorem for deciding matrix growth

Describes a project that uses

Uses Software

• TPDB

This page was built for publication: Revisiting matrix interpretations for polynomial derivational complexity of term rewriting

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