Revisiting Matrix Interpretations for Polynomial Derivational Complexity of Term Rewriting

DOI10.1007/978-3-642-16242-8_39zbMath1306.68083OpenAlexW1568532679MaRDI QIDQ4933331

Aart Middeldorp, Harald Zankl, Friedrich Neurauter

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)

Related Items (7)

Uncurrying for termination and complexity ⋮ 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 ⋮ Derivational complexity and context-sensitive Rewriting ⋮ Analyzing innermost runtime complexity of term rewriting by dependency pairs

Uses Software

• TPDB

This page was built for publication: Revisiting Matrix Interpretations for Polynomial Derivational Complexity of Term Rewriting