Beniamino Accattoli ; Ugo Dal Lago ; Gabriele Vanoni - Reasonable Space for the ${\lambda}$-Calculus, Logarithmically

lmcs:10883 - Logical Methods in Computer Science, November 20, 2024, Volume 20, Issue 4 - https://doi.org/10.46298/lmcs-20(4:15)2024
Reasonable Space for the ${\lambda}$-Calculus, LogarithmicallyArticle

Authors: Beniamino Accattoli ; Ugo Dal Lago ; Gabriele Vanoni

Can the $\lambda$-calculus be considered a reasonable computational model?
Can we use it for measuring the time $\textit{and}$ space consumption of algorithms? While the literature contains positive answers about time, much less is known about space. This paper presents a new reasonable space cost model for the $\lambda$-calculus, based on a variant over the Krivine abstract machine. For the first time, this cost model is able to accommodate logarithmic space. Moreover, we study the time behavior of our machine and show how to transport our results to the call-by-value $\lambda$-calculus.

https://doi.org/10.46298/lmcs-20(4:15)2024
Source: arXiv.org:2203.00362
Volume: Volume 20, Issue 4
Secondary volumes: Selected Papers of the 37th ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
Published on: November 20, 2024
Imported on: February 1, 2023
Keywords: Computer Science - Logic in Computer Science, Computer Science - Computational Complexity, Computer Science - Programming Languages
Licence: Attribution 4.0 International (CC BY 4.0)
Funding:
    Source : OpenAIRE Graph
  • Differential Program Semantics; Funder: European Commission; Code: 818616
  • MathInGreaterParis Fellowship Programme; Funder: European Commission; Code: 101034255

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

Share and export

Consultation statistics

This page has been seen 2570 times.
This article's PDF has been downloaded 466 times.