This special issue of Mathematical Structures in Computer Science is devoted to recent work in subtyping. When subtyping was first proposed, it presented a new vehicle for understanding programming languages, together with challenging theoretical issues. The papers in this special issue include a new approach to the decidability of subtyping, a metatheoretic investigation of transitivity of coercive subtyping for parametrised dependent types, and applications of subtyping to the classic programming language concerns of flow analysis and typing for distributed systems. We believe that the scope of the papers demonstrates convincingly that the theory and practice of subtyping continue to be extended in novel and interesting ways.

This paper gives the first proof that the subtyping relation of a higher-order lambda calculus, -equality, which is apparently the first such, and shows its equivalence with the traditional presentation.

This paper outlines an elementary approach for showing the decidability of type checking for type theories with βη-equality, relevant to foundations for modules systems and type theory-based proof systems. The key to the approach is a syntactic translation mapping terms in the βη presentation into their full η-expansions in the β presentation. Decidability of type checking is lifted from the target β presentation to the βη presentation. The approach extends to other inductive kinds with a single constructor, and is demonstrated for singletons and dependent pairs.