An Invariant Cost Model for the Lambda Calculus
| dc.creator | Lago, Ugo Dal | |
| dc.creator | Martini, Simone | |
| dc.date | 2005-11-12 | |
| dc.date.accessioned | 2026-07-07T06:49:35Z | |
| dc.date.available | 2026-07-07T06:49:35Z | |
| dc.description | We define a new cost model for the call-by-value lambda-calculus satisfying the invariance thesis. That is, under the proposed cost model, Turing machines and the call-by-value lambda-calculus can simulate each other within a polynomial time overhead. The model only relies on combinatorial properties of usual beta-reduction, without any reference to a specific machine or evaluator. In particular, the cost of a single beta reduction is proportional to the difference between the size of the redex and the size of the reduct. In this way, the total cost of normalizing a lambda term will take into account the size of all intermediate results (as well as the number of steps to normal form). | |
| dc.description | 19 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0511045 | |
| dc.identifier | http://arxiv.org/abs/cs/0511045 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/104403 | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Computational Complexity | |
| dc.subject | F.4.1 | |
| dc.title | An Invariant Cost Model for the Lambda Calculus | |
| dc.type | text |