On the complexity of normalization for the planar $\lambda$-calculus

Anupam Das, Damiano Mazza, Lê Thành Dũng Nguyên +1

We sketch a tentative proof of P-completeness for the $\beta$-convertibility problem on untyped planar (a.k.a. ordered or non-commutative) $\lambda$-terms.