Principal Typing for Intersection Types, Forty-Five Years Later
Electronic Proceedings in Theoretical Computer Science · 04.03.2026 · 441 · 227-250
DOI: 10.4204/eptcs.441.14 ↗Kurz gefasst
Fachartikel in der Zeitschrift Electronic Proceedings in Theoretical Computer Science, online erschienen am 04.03.2026. Verfasst von Daniele Pautasso und 1 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben.
Abstract (Originalsprache)
A type assignment system for lambda-calculus enjoys the principal typing property if every typable term M has a special typing, called principal, from which all typings for M can be obtained via suitable operations. The existence of principal typings in various intersection type disciplines has long been established using both semantical and syntactical approaches. Historically, on the syntactical side, proofs of this property and the description of type inference (semi-)algorithms computing principal typings have been complicated by many subtle technicalities; the present work aims at providing a more accessible formulation. To this end, we revisit some classical notions, and identify three elementary operations (substitution, expansion, erasure) that allow to build any type derivation in a system characterizing head normalization. We then use such operations in the design of an inference semi-algorithm that computes the principal typing of all and only the strongly normalizing terms, thus contributing to a modern perspective on results originally proven more than 40 years ago
Zitieren
APA
Pautasso, D., & Rocca, S. R. D. (2026). Principal Typing for Intersection Types, Forty-Five Years Later. Electronic Proceedings in Theoretical Computer Science, 441, 227-250. https://doi.org/10.4204/eptcs.441.14
Vancouver
Pautasso D, Rocca SRD. Principal Typing for Intersection Types, Forty-Five Years Later. Electronic Proceedings in Theoretical Computer Science. 2026;441:227-250. doi:10.4204/eptcs.441.14
BibTeX
@article{Pautasso2026,
author = {Pautasso, Daniele and Rocca, Simona Ronchi Della},
title = {Principal Typing for Intersection Types, Forty-Five Years Later},
journal = {Electronic Proceedings in Theoretical Computer Science},
year = {2026},
volume = {441},
pages = {227--250},
doi = {10.4204/eptcs.441.14}
}
EUVIMED