cl-banner

Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems

Aart Middeldorp, Georg Moser, Friedrich Neurauter, Johannes Waldmann, and Harald Zankl

Proceedings 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.

 

  PDF |    doi:10.1007/978-3-642-21493-6_1  | © Springer

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
}
Nach oben scrollen