Exponential automatic amortized resource analysis

DOI10.1007/978-3-030-45231-5_19OpenAlexW3009691493MaRDI QIDQ2200835FDOQ2200835

Authors: David M. Kahn, Jan Hoffmann 

Publication date: 23 September 2020

Full work available at URL: https://arxiv.org/abs/2002.09519

Recommendations

• Two decades of automatic amortized resource analysis
• Type-based amortized resource analysis with integers and arrays
• Type-based amortized resource analysis with integers and arrays
• Multivariate amortized resource analysis
• Amortized resource analysis with polynomial potential. A static inference of polynomial bounds for functional programs

zbMATH Keywords

functional programmingStirling numbersexponentialquantitative analysisresource consumptionamortized analysis

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites Work

• A theory of type polymorphism in programming
• Partial-order methods for the verification of concurrent systems. An approach to the state-explosion problem
• Title not available (Why is that?)
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• A calculus of communicating systems
• Results on the propositional \(\mu\)-calculus
• A stubborn attack on state explosion
• Combining partial-order reductions with on-the-fly model-checking.
• Invariants for the construction of a handshake register
• Confluence for process verification
• A partial order approach to branching time logic model checking.
• Parameterised Boolean equation systems
• Amortized Computational Complexity
• Mechanical program analysis
• Contract-based resource verification for higher-order functions with memoization
• Amortized complexity verified
• Title not available (Why is that?)
• Complexity and resource bound analysis of imperative programs using difference constraints
• Stubborn set reduction for two-player reachability games
• Partial order reduction for reachability games
• Stubborn set intuition explained
• Liveness analysis for parameterised Boolean equation systems
• Proof graphs for parameterised Boolean equation systems
• Weakest precondition reasoning for expected run-times of probabilistic programs
• Partial-order reduction in the weak modal mu-calculus
• The inconsistent labelling problem of stutter-preserving partial-order reduction
• Type-Based Allocation Analysis for Co-recursion in Lazy Functional Languages
• Partial order reduction for checking LTL formulae with the next-time operator
• Title not available (Why is that?)
• Automatic Space Bound Analysis for Functional Programs with Garbage Collection

Cited In (4)

• Synthesis with asymptotic resource bounds
• Two decades of automatic amortized resource analysis
• Preface: Special issue on automatic resource bound analysis
• Type-based analysis of logarithmic amortised complexity

This page was built for publication: Exponential automatic amortized resource analysis

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