POPL 2026
Sun 11 - Sat 17 January 2026 Rennes, France
Fri 16 Jan 2026 14:25 - 14:50 at Réfectoire - Proof Assistants 2 Chair(s): Matthieu Sozeau

In a dependent type theory with $\beta$-equivalence as its equational theory, the confluence of untyped reduction and termination immediately give us a proof of the decidability of type conversion, where the decision procedure for convertibility simply checks the equality of the $\beta$-normal forms of its inputs. This technique is not available in the presence of surjective pairing (i.e. the $\eta$-law for pairs) because $\beta\eta$-reduction is not confluent. In this work, we show that by adopting established syntactic techniques, we can resolve the issue with confluence caused by surjective pairing, and recover a confluence-based proof of decidability of type conversion. Compared to existing proof developments, which rely on semantic tools such as Kripke-style logical relations, our proof modularly composes a minimal semantic proof of untyped normalization and a syntactic proof of decidability. This modularity enables us to explore algorithmic conversion through syntactic methods without modifying the minimal semantic proof. We have fully mechanized our results using the Rocq theorem prover.

Fri 16 Jan

Displayed time zone: Brussels, Copenhagen, Madrid, Paris change

14:00 - 15:40
Proof Assistants 2POPL at Réfectoire
Chair(s): Matthieu Sozeau Inria
14:00
25m
Talk
AdapTT: Functoriality for Dependent Type Casts
POPL
Arthur Adjedj ENS Paris Saclay, Université Paris-Saclay, Meven Lennon-Bertrand Inria – Université Paris Cité, Thibaut Benjamin Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, Kenji Maillard Inria
DOI
14:25
25m
Talk
Algorithmic Conversion with Surjective Pairing: A Syntactic and Untyped Approach
POPL
Yiyun Liu University of Pennsylvania, Stephanie Weirich University of Pennsylvania
DOI
14:50
25m
Talk
Encode the Cake and Eat It Too: Controlling Computation in Type Theory, LocallyDistinguished Paper
POPL
Yann Leray Nantes Université; Inria, Théo Winterhalter INRIA
DOI
15:15
25m
Talk
Normalisation for First-Class Universe LevelsDistinguished PaperRemote
POPL
Nils Anders Danielsson University of Gothenburg, Naïm Camille Favier Chalmers University of Technology and University of Gothenburg, Ondřej Kubánek Chalmers University of Technology
DOI