DROPS

Document

A Note on Logical PERs and Reducibility. Logical Relations Strike Again!

Authors: Jean Gallier

Published in: OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024)

Abstract

We prove a general theorem for establishing properties expressed by binary relations on typed (first-order) λ-terms, using a variant of the reducibility method and logical PERs. As an application, we prove simultaneously that β-reduction in the simply-typed λ-calculus is strongly normalizing, and that the Church-Rosser property holds (and similarly for βη-reduction).

Cite as

Jean Gallier. A Note on Logical PERs and Reducibility. Logical Relations Strike Again!. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gallier:OASIcs.Tannen.7,
  author =	{Gallier, Jean},
  title =	{{A Note on Logical PERs and Reducibility. Logical Relations Strike Again!}},
  booktitle =	{The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen},
  pages =	{7:1--7:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-320-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{119},
  editor =	{Amarilli, Antoine and Deutsch, Alin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.7},
  URN =		{urn:nbn:de:0030-drops-201033},
  doi =		{10.4230/OASIcs.Tannen.7},
  annote =	{Keywords: Typed lambda-calculus, reducibility, logical relations, per’s, strong normalization, Church-Rosser property}
}

Search Results

Documents authored by Gallier, Jean

A Note on Logical PERs and Reducibility. Logical Relations Strike Again!

Abstract

Cite as

Thanks for your feedback!

Could not send message