paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Finiteness and rational sequences, constructively

有限性与有理序列:构造性方法
JFP vol.272017匹配度 2/10 · 该论文属于Martin–Löf类型论与定理证明中的构造性形式化工作,但与用户关注的PL与AI/LLM交叉、静态分析、浮点程序分析、贝叶斯程序分析等核心方向均无直接关联,仅在形式化验证/类型系统背景上有很弱的联系。引用 4 inbox
TARMO UUSTALU, NICCOLÒ VELTRI
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:在Martin–Löf类型论中构造性地实现有理序列,证明两种有限性概念可互换,并引入带回溯指针的列表。

有理序列是可能无限、但只有有限多个不同后缀的序列。本文在Martin–Löf类型论中给出其多种构造性实现。首先,作者把有理序列的定义直接翻译为类型论语言,构造表达后缀集合有限性的谓词;由于类型论中存在多种不等价的有限性概念,他们考察listability与Noetherianness,并证明在有理序列的实现中二者可以互换。随后,他们引入带回溯指针的列表,作为有理序列的归纳实现,并建立双向转换:带回溯指针的列表可展开为有理序列,有理序列可截断为带回溯指针的列表。最后,以有理数的分数表示与十进制表示相互转换为例说明该实现。

问题
如何在Martin–Löf类型论中构造性地表示可能无限但只有有限多个不同后缀的有理序列,并处理不同有限性概念之间的关系。
方法
将有理序列定义翻译为类型论中的有限性谓词,比较listability与Noetherianness,并引入带回溯指针的列表以建立归纳实现与相互转换。
评估
在类型论中形式化定义并证明两种有限性概念可互换,并通过有理数分数与十进制表示转换的示例展示该方法。
原文摘要(Abstract)

Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we literally translate the above definition of rational sequence into the language of type theory, i.e., we construct predicates on possibly infinite sequences expressing the finiteness of the set of suffixes. In type theory, there exist several inequivalent notions of finiteness. We consider two of them, listability and Noetherianness, and show that in the implementation of rational sequences the two notions are interchangeable. Then we introduce the type of lists with backpointers, which is an inductive implementation of rational sequences. Lists with backpointers can be unwound into rational sequences, and rational sequences can be truncated into lists with backpointers. As an example, we see how to convert the fractional representation of a rational number into its decimal representation and vice versa.

链接与引用

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

BibTeX
@article{UustaluV17,
  title = {Finiteness and rational sequences, constructively},
  author = {TARMO UUSTALU and NICCOLÒ VELTRI},
  journal = {Journal of Functional Programming},
  volume = {27},
  year = {2017},
  doi = {10.1017/s0956796817000041}
}