Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems
From MaRDI portal
Publication:3014928
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
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
