On the complexity of normalization for the planar λ-calculus

Reference. On the complexity of normalization for the planar $𝜆$ -calculus

Anupam Das, Damiano Mazza, Lê Thành Dũng Nguyên, Noam Zeilberger · arXiv · 2024 · complexity · arXiv

We sketch a tentative proof of P-completeness for the

𝛽

-convertibility problem on untyped planar (a.k.a. ordered or non-commutative)

𝜆

-terms.

Cite

Cite as @das-2024-on (helia, typst) · \cite{das-2024-on} (LaTeX)

BibTeX

bibtex · 8 lines

@misc{das-2024-on,
  author = {Anupam Das and Damiano Mazza and Lê Thành Dũng Nguyên and Noam Zeilberger},
  title = {On the complexity of normalization for the planar λ-calculus},
  year = {2024},
  month = {4},
  eprint = {2404.05276},
  archiveprefix = {arXiv}
}

hayagriva YAML (typst)

yaml · 11 lines

das-2024-on:
  type: misc
  title: On the complexity of normalization for the planar λ-calculus
  author:
  - Das, Anupam
  - Mazza, Damiano
  - Nguyên, Lê Thành Dũng
  - Zeilberger, Noam
  date: 2024-04
  serial-number:
    arxiv: '2404.05276'

Download: das-2024-on.bib · das-2024-on.yml

Cites 8 works (1 here)

With notes (1)

The mathematics of sentence structure lambek58Amer. Math. Monthly · 1958

DOI

External (7)