Lune

POPL2026Top-tier venue

Canonicity for Indexed Inductive-Recursive Types

András Kovács

Abstract

We prove canonicity for a Martin-Löf type theory with a countable universe hierarchy where each universe supports indexed inductive-recursive (IIR) types. We proceed in two steps. First, we construct IIR types from inductive-recursive (IR) types and other basic type formers, in order to simplify the subsequent canonicity proof. The constructed IIR types support the same definitional computation rules that are available in Agda’s native IIR implementation. Second, we give a canonicity proof for IR types, building on the established method of gluing along the global sections functor. The main idea is to encode the canonicity predicate for each IR type using a metatheoretic IIR type.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Normalization for Multimodal Type Theory cites Normalization for Cubical Type Theory
  • Internal Parametricity, without an Interval cites Normalization for Multimodal Type Theory
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on5

  1. Normalization for Cubical Type TheoryJonathan Sterling, Carlo AngiuliLICS 2021 · 28 citations
  2. The taming of the rew: a type theory with computational assumptionsJesper Cockx, Nicolas Tabareau, Théo WinterhalterPOPL 2021 · 24 citations
  3. Normalization for Multimodal Type TheoryDaniel GratzerLICS 2022 · 23 citations
  4. Impredicative Observational EqualityLoïc Pujet, Nicolas TabareauPOPL 2023 · 14 citations
  5. Internal Parametricity, without an IntervalThorsten Altenkirch, Yorgo Chamoun, Ambrus Kaposi, Michael ShulmanPOPL 2024 · 4 citations

Related papers

  1. Primitive Recursive Dependent Type TheoryUlrik Torben Buchholtz, Johannes Schipp von BranitzLICS 2024
  2. Definitional Proof Irrelevance Made AccessibleThiago Felicissimo, Yann Leray, Loïc Pujet, Nicolas Tabareau et al.LICS 2026
  3. All Your Base Are Belong to Us: Sort Polymorphism for Proof AssistantsJosselin Poiret, Gaëtan Gilbert, Kenji Maillard, Pierre-Marie Pédrot et al.POPL 2025 · 6 citations
  4. Large and Infinitary Quotient Inductive-Inductive TypesAndrás Kovács, Ambrus KaposiLICS 2020 · 7 citations
  5. Normalisation for First-Class Universe LevelsNils Anders Danielsson, Naïm Camille Favier, Ondrej KubánekPOPL 2026 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines