← All problems
Unverified

Higher-Order Matching with Many Atoms

Allow simple types to be built from an arbitrary finite set of atomic type variables rather than one atom.

  1. Is higher-order matching decidable in this many-atom setting?

  2. Given types ρ\rho and τ\tau, is it decidable whether ρ\rho is a retract of τ\tau, meaning that there are typed terms F:ρ→τF:\rho\to\tau and G:τ→ρG:\tau\to\rho with G∘F=βηIρG\circ F=_{\beta\eta}I_\rho?

  3. In the polymorphic setting, does mutual retraction ρ◃τ\rho\triangleleft\tau and τ◃ρ\tau\triangleleft\rho imply that ρ\rho and τ\tau are isomorphic?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu