Complexity analysis by graph rewriting

DOI10.1007/978-3-642-12251-4_19MaRDI QIDQ3558343zbMATH OpenOpenAlexFDO

Authors Martin Avanzini, Georg Moser

Publication date 4 May 2010

Published in Functional and Logic Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-12251-4_19

Mathematics Subject Classification ID

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

Recommendations

• Closing the gap between runtime complexity and polytime computability
• Complexity of acyclic term graph rewriting
• Complexity analysis for term rewriting by integer transition systems
• Analyzing runtime complexity via innermost runtime complexity
• scientific article; zbMATH DE number 177461

Cited in

(15)

• Comparison of two graph-rewrite systems
• The exact hardness of deciding derivational and runtime complexity
• Computing cyclomatic complexity with cubic flowgraphs
• Complexity Analysis by Rewriting
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• Closing the gap between runtime complexity and polytime computability
• Automated Implicit Computational Complexity Analysis (System Description)
• A new order-theoretic characterisation of the polytime computable functions
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Estimation of expressions' complexities for two-terminal directed acyclic graphs
• Constant runtime complexity of term rewriting is semi-decidable
• Complexity of acyclic term graph rewriting
• Complexity analysis of precedence terminating infinite graph rewrite systems
• Automated complexity analysis based on ordered resolution
• scientific article; zbMATH DE number 4074465 (Why is no real title available?)

This page was built for publication: Complexity analysis by graph rewriting

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