A combination framework for complexity

DOI10.1016/J.IC.2015.12.007MaRDI QIDQ276251zbMATH OpenOpenAlexFDO

Authors Martin Avanzini, Georg Moser

Publication date 3 May 2016

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2015.12.007

zbMATH Keywords

automationresource analysisruntime complexityterm rewriting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• A combination framework for complexity
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Automated Complexity Analysis Based on the Dependency Pair Method
• Modular complexity analysis via relative complexity

Cites work

• A combination framework for complexity
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• A new order-theoretic characterisation of the polytime computable functions
• A new recursion-theoretic characterization of the polytime functions
• Algorithms with polynomial interpretation termination proof
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Automated Complexity Analysis Based on Context-Sensitive Rewriting
• Automated Complexity Analysis Based on the Dependency Pair Method
• Automatic type inference for amortised heap-space analysis
• Closing the gap between runtime complexity and polytime computability
• Complexity analysis of term rewriting based on matrix and context dependent interpretations
• Complexity analysis of term-rewriting systems
• Complexity, Graphs, and the Dependency Pair Method
• Joint spectral radius theory for automated complexity analysis of rewrite systems
• Modular complexity analysis via relative complexity
• Modular termination proofs for rewriting using dependency pairs
• Monotonicity constraints for termination in the integer domain
• Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs
• Multivariate amortized resource analysis
• On constructor rewrite systems and the lambda calculus
• POP* and Semantic Labeling Using SAT
• Polynomial path orders
• Quasi-interpretation Synthesis by Decomposition
• Rewriting Techniques and Applications
• Termination of term rewriting using dependency pairs
• Termination proofs and the length of derivations
• The Derivational Complexity Induced by the Dependency Pair Method
• The size-change principle for program termination
• Tyrolean Complexity Tool: Features and Usage.
• Uncurrying for termination and complexity

Cited in

(14)

• On complexity bounds and confluence of parallel term rewriting
• A combination framework for complexity
• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• Read/write factorizable programs
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• Modular complexity analysis via relative complexity
• Analysing parallel complexity of term rewriting
• Synergetic methods of data complexation
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Kruskal's tree theorem for acyclic term graphs
• Type-based analysis of logarithmic amortised complexity
• From Jinja bytecode to term rewriting: a complexity reflecting transformation
• Runtime complexity analysis of logically constrained rewriting
• Automated Complexity Analysis Based on the Dependency Pair Method

Describes a project that uses

Uses Software

• Tyrolean

This page was built for publication: A combination framework for complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q276251)