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 Entry

@inproceedings{MMNWZ-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,
 doi       = "10.1007/978-3-642-21493-6\_1"
}