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
    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 2275 times.
    This article's PDF has been downloaded 369 times.