paperbot · PL 论文追踪

RSS

Non-idempotent types for classical calculi in natural deduction style

LMCS vol.Volume 16, Issue 12020引用 14
Delia Kesner, Pierre Vial

尚未生成 AI 速览(可能缺少 API key 或等待下次运行补跑)。

原文摘要(Abstract)

In the first part of this paper, we define two resource aware typing systems for the {\lambda}{\mu}-calculus based on non-idempotent intersection and union types. The non-idempotent approach provides very simple combinatorial arguments-based on decreasing measures of type derivations-to characterize head and strongly normalizing terms. Moreover, typability provides upper bounds for the lengths of the head reduction and the maximal reduction sequences to normal-form. In the second part of this paper, the {\lambda}{\mu}-calculus is refined to a small-step calculus called {\lambda}{\mu}s, which is inspired by the substitution at a distance paradigm. The {\lambda}{\mu}s-calculus turns out to be compatible with a natural extensionof the non-idempotent interpretations of {\lambda}{\mu}, i.e., {\lambda}{\mu}s-reduction preserves and decreases typing derivations in an extended appropriate typing system. We thus derive a simple arithmetical characterization of strongly {\lambda}{\mu}s-normalizing terms by means of typing.

链接与引用

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

BibTeX
@article{KesnerV19,
  title = {Non-idempotent types for classical calculi in natural deduction style},
  author = {Delia Kesner and Pierre Vial},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 1},
  year = {2020},
  doi = {10.23638/lmcs-16(1:3)2020}
}