Analyzing runtime complexity via innermost runtime complexity

DOI10.29007/1NBHMaRDI QIDQ4645739zbMATH OpenOpenAlexFDO

Authors Florian Frohn, Jürgen Giesl

Publication date 10 January 2019

Published in EPiC Series in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.29007/1nbh

zbMATH Keywords

term rewritingevaluation strategiesautomated complexity analysis

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Complexity analysis for term rewriting by integer transition systems
• Inferring lower bounds for runtime complexity
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• Lower bounds for runtime complexity of term rewriting

Cited in

(12)

• Analysing parallel complexity of term rewriting
• Complexity analysis for term rewriting by integer transition systems
• Automated amortised resource analysis for term rewrite systems
• Complexity analysis by graph rewriting
• Inferring lower bounds for runtime complexity
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• From innermost to full almost-sure termination of probabilistic term rewriting
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• From innermost to full probabilistic term rewriting: almost-sure termination, complexity, and modularity
• Constant runtime complexity of term rewriting is semi-decidable
• Lower bounds for runtime complexity of term rewriting
• Analyzing Innermost Runtime Complexity Through Tuple Interpretations

This page was built for publication: Analyzing runtime complexity via innermost runtime complexity

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