← All problems
Unverified

Tree Representations of Contextual Equivalence

For a set P\mathcal{P} of lambda terms, define M∼PNM\sim_{\mathcal{P}}N when, for every one-hole context C[ ⋅ ]C[\,\cdot\,], C[M]C[M] beta-reduces to a member of P\mathcal{P} if and only if C[N]C[N] does. Find a tree representation whose equality is exactly ∼P\sim_{\mathcal{P}} for each of the following choices:

  1. P=W\mathcal{P}=\mathcal{W}, the weak-head normal forms;

  2. P=T\mathcal{P}=\mathcal{T}, the top normal forms;

  3. P=SA\mathcal{P}=\mathcal{SA}, the strongly active terms;

  4. P=SAX\mathcal{P}=\mathcal{SA}_X, the strongly active terms depending on a fixed set XX of lambda terms;

  5. P=HA\mathcal{P}=\mathcal{HA}, the head-active terms.

Coming soon

Organizer

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