Derivational Complexity Is an Invariant Cost Model

DOI10.1007/978-3-642-15331-0_7zbMath1305.68107OpenAlexW1883234726MaRDI QIDQ5747633

Simone Martini, Ugo Dal Lago

Publication date: 14 September 2010

Published in: Foundational and Practical Aspects of Resource Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15331-0_7

Mathematics Subject Classification ID

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

Related Items (8)

Higher-order interpretations and program complexity ⋮ The Negligible and Yet Subtle Cost of Pattern Matching ⋮ On sharing, memoization, and polynomial time ⋮ Game semantics approach to higher-order complexity ⋮ A Fresh Look at the λ-Calculus ⋮ (In)efficiency and reasonable cost models ⋮ Real or natural number interpretation and their effect on complexity ⋮ Characterizing polynomial time complexity of stream programs using interpretations

This page was built for publication: Derivational Complexity Is an Invariant Cost Model