Impredicativity in Linear Dependent Type Theory

Sam L. Speight, Niels van der Weide · 2026

Read Impredicativity in Linear Dependent Type Theory by Sam L. Speight, Niels van der Weide (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-08846.txt.

Description

Sam Speight and one co-author build a mathematical model for a type theory that mixes linear and ordinary reasoning. Linear types track resources that must be used exactly once, while ordinary types allow reuse. Their model grows out of a linear combinatory algebra, a spare algebraic setting for computation.

To make the model work, they add a universe with two decoding rules, one for each kind of type, closed under large products of both kinds. They also add a rule for turning linear terms into ordinary ones. Lists over a linear type serve as a case study, and the whole construction is checked in the Rocq proof assistant.

Catalog record

CREATORSam L. Speight, Niels van der Weide
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-08846

Browse the full library · About the Tower of Babel