Metraipolis › archive › dc_8d253f26b70e

Typechecking without Minimum Types: Finite Bases and Backward Checking for $F_{<:}^{\top}$ — arXiv:2610.20356

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.20356
License (as archived)
CC0-1.0
Archived
2026-10-15T14:40:31.757Z
SHA-256 of the archived text
3f4a3ec12d194d762680c303f42a7a1f208b23a1b981c3f341a8128c56971153
Stable URL of this page
https://metraipolis.com/documento/dc_8d253f26b70e

How to cite

Typechecking without Minimum Types: Finite Bases and Backward Checking for $F_{<:}^{\top}$ — arXiv:2610.20356 — arXiv (en), https://arxiv.org/abs/2610.20356 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8d253f26b70e (Metraipolis archive dc_8d253f26b70e, sha256 3f4a3ec12d194d762680c303f42a7a1f208b23a1b981c3f341a8128c56971153)
BibTeX
@misc{dc8d253f26b70e,
  title = {Typechecking without Minimum Types: Finite Bases and Backward Checking for $F_<:^top$ — arXiv:2610.20356},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.20356},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8d253f26b70e; sha256 3f4a3ec12d194d762680c303f42a7a1f208b23a1b981c3f341a8128c56971153},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20356. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

System $F_{<:}^{\top}$ has decidable subtyping but lacks minimum types. We prove that typechecking is decidable for arbitrary explicitly annotated terms with unrestricted subsumption. The difficulty is that type abstraction uses a variable's declared bound to type its body, while quantified subtyping forgets that bound. We construct finite covers that preserve all required subtype comparisons across this change of context. These covers yield a compositional finite typing basis and a decision procedure. We then derive a backward checker that propagates acceptable targets without constructing the complete typing basis. Rectangularity of typing families gives a uniform elimination domain while retaining every result type, even when the canonical type is not least. Finite inverse families transport targets through type substitution. The same inverse specification recovers bound forgetting and yields finite type-avoidance families. Both typechecking procedures are total Rocq functions proved equivalent to the original typing judgment. For a separate symbolic word-RAM realization, we prove a quartic worst-case work bound. We measure family representation sizes and comparison storage in independent OCaml prototypes on synthetic checking judgments.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.PL, nuovi lavori del giorno).
Categorie arXiv: Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2610.20356 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T14:00:24.238Z dalla pagina https://arxiv.org/list/cs.PL/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).