Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems

DOI10.1007/978-3-642-21493-6_1zbMath1307.68042OpenAlexW172021561MaRDI QIDQ3014928

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

Publication date: 8 July 2011

Published in: Algebraic Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21493-6_1

zbMATH Keywords

joint spectral radiusweighted automataderivational complexitymatrix interpretations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Grammars and rewriting systems (68Q42)

Related Items

A combination framework for complexity, Unnamed Item, From Jinja bytecode to term rewriting: a complexity reflecting transformation, Uncurrying for termination and complexity, A Perron-Frobenius theorem for deciding matrix growth, A new order-theoretic characterisation of the polytime computable functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A gap result for the norms of semigroups of matrices
• Handbook of weighted automata
• On tree automata that certify termination of left-linear term rewriting systems
• Matrix interpretations for proving termination of term rewriting
• On the degree of ambiguity of finite automata
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Satisfiability of Non-linear (Ir)rational Arithmetic
• Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations
• Arctic Termination ...Below Zero
• Automated Complexity Analysis Based on the Dependency Pair Method
• Term Rewriting and All That
• Revisiting Matrix Interpretations for Polynomial Derivational Complexity of Term Rewriting
• POLYNOMIALLY BOUNDED MATRIX INTERPRETATIONS
• Modular Complexity Analysis via Relative Complexity
• The Derivational Complexity Induced by the Dependency Pair Method