### Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems

Aart Middeldorp, Georg Moser, Friedrich Neurauter, Johannes Waldmann, and Harald ZanklProceedings of the 4th International Conference on Algebraic Informatics (CAI 2011), Lecture Notes in Computer Science 6742, pp. 1 – 20, 2011.

### Abstract

Matrix interpretations can be used to bound the derivational complexity of

term rewrite systems. In particular, triangular matrix interpretations over

the natural numbers are known to induce polynomial upper bounds on the

derivational complexity of (compatible) rewrite systems. Recently two

different improvements were proposed, based on the theory of weighted

automata and linear algebra. In this paper we strengthen and unify these

improvements by using joint spectral radius theory.

### BibTeX

@inproceedings{AMGMFNJWHZ-CAI11, author = "Aart Middeldorp and Georg Moser and Friedrich Neurauter and Johannes Waldmann and Harald Zankl", title = "Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems", booktitle = "Proceedings of the 4th International Conference on Algebraic Informatics", series = "Lecture Notes in Computer Science", volume = 6742, pages = "1--20", year = 2011 }