Lune

POPL2026Top-tier venue

Algorithmic Conversion with Surjective Pairing: A Syntactic and Untyped Approach

Yiyun Liu, Stephanie Weirich

Abstract

In a dependent type theory with β -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 β -normal forms of its inputs. This technique is not available in the presence of surjective pairing (i.e. the η -law for pairs) because β η -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.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Normalization for Cubical Type TheoryJonathan Sterling, Carlo AngiuliLICS 2021 · 28 citations
  2. Definitional Proof Irrelevance Made AccessibleThiago Felicissimo, Yann Leray, Loïc Pujet, Nicolas Tabareau et al.LICS 2026
  3. Consistency of a Dependent Calculus of IndistinguishabilityYiyun Liu, Jonathan Chan, Stephanie WeirichPOPL 2025 · 3 citations
  4. Impredicative Observational EqualityLoïc Pujet, Nicolas TabareauPOPL 2023 · 14 citations
  5. Normalization for Multimodal Type TheoryDaniel GratzerLICS 2022 · 23 citations
Dusk over the sea between two cliffs drawn in fine vertical lines