The Inhabitation Problem for Rank Two Intersection Types

2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/121214We prove that the inhabitation problem for rank two intersection types is decidable, but (contrary to common belief) EXPTIME-hard. The exponential time hardness is shown by reduction from the in-place acceptance problem for alternating Turing machines.15 pagesLogic in Computer ScienceThe Inhabitation Problem for Rank Two Intersection Typestext