一句话：提出基于 Krivine 抽象机变体的 λ-演算合理空间代价模型，首次支持对数空间，并迁移到 call-by-value。
本文研究 λ-演算能否作为合理的计算模型，以同时度量算法的时间与空间消耗。已有工作对时间开销模型给出了肯定答案，但空间开销模型仍不清楚。作者提出一种新的 λ-演算合理空间代价模型，其基础是 Krivine 抽象机的一个变体；该模型首次能够容纳对数空间计算。作者还分析了该抽象机的时间行为，并说明如何将所得结果迁移到按值调用（call-by-value）λ-演算。结果表明，在 λ-演算中可以定义满足合理性的空间复杂度度量，且与对数空间这一重要复杂度类兼容。
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.
@article{paperbot2707,
title = {Reasonable Space for the ${\lambda}$-Calculus, Logarithmically},
author = {Beniamino Accattoli and Ugo Dal Lago and Gabriele Vanoni},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 4},
year = {2024},
doi = {10.46298/lmcs-20(4:15)2024}
}