paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Reasonable Space for the λ-Calculus, Logarithmically

λ演算的合理空间:对数级
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 2/10 · 论文属于纯 λ 演算与抽象机的空间复杂性理论研究,未涉及 LLM/Agent、机器学习系统静态分析、浮点程序分析或贝叶斯程序分析等核心方向。引用 4 inbox
Beniamino Accattoli, Ugo Dal Lago, Gabriele Vanoni
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出基于Krivine抽象机变体的λ演算空间代价模型,首次支持对数空间,并研究其时间行为与call-by-value移植。

本文探讨λ演算能否作为合理的计算模型,特别是能否度量算法的空间消耗。既有文献对时间消耗已给出肯定答案,但空间方面所知甚少。作者提出一种新的λ演算合理空间代价模型,其基础是Krivine抽象机的一个变体。该模型首次能够容纳对数空间。论文还分析该机器的时间行为,并说明如何将相关结果迁移到call-by-value λ演算。这一工作为λ演算中的空间复杂度与合理代价语义提供了新方案。

问题
λ演算能否作为合理计算模型,并用于度量算法的时间与空间消耗?时间方面已有肯定答案,但空间方面仍缺乏合理代价模型。
方法
提出基于Krivine抽象机变体的新合理空间代价模型,分析该机器的时间行为,并将结果迁移到call-by-value λ演算。
评估
通过定义并分析抽象机代价模型进行理论评估:该模型首次支持对数空间,且时间行为与call-by-value迁移均得到论证。
原文摘要(Abstract)

Can the λ-calculus be considered a reasonable computational model? Can we use it for measuring the time 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 λ-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 λ-calculus.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{AccattoliLV22,
  title = {Reasonable Space for the λ-Calculus, Logarithmically},
  author = {Beniamino Accattoli and Ugo Dal Lago and Gabriele Vanoni},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533362}
}