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
}