Laboratoire d'informatique de l'École polytechnique

Talk by Jui-Hsuan: « A positive perspective on term representation »

Speaker: Jui-Hsuan
Location: Online
Date: Mon, 27 Jun 2022, 14:00-15:00

For a new seminar on the proofs and algorithms pole of LIX, we are happy to welcome Jui-Hsuan Wu (one of our own Ph.D. students at LIX), invited by the PARTOUT team.

Note that this talk is the last one in PARTOUT before the summer holidays. We will resume our seminar in September.

Abstract: The structure of terms and expressions are represented variously via, say, labeled trees or directed acyclic graphs (DAGs). When such expressions contain bindings, additional devices are needed. In this talk, I will present the focused proof system LJF as a framework for describing term structures and substitution. Since the proof theory of LJF does not pick a canonical polarization for primitive types, two different approaches to term representation arise. When primitive types are given the negative bias, LJF proofs encode term structures as tree-like structures in a familiar fashion. In this situation, cut elimination also yields the familiar notion of substitution. On the other hand, when primitive types are given the positive bias, LJF proofs yield a structure in which explicit sharing of term structures is possible. In this situation, cut elimination yields a different notion of substitution. To illustrate these two approaches to term representation, I will give an example by applying them to the encoding of untyped λ-terms.

Join Zoom Meeting

The list of next seminars can be found at:

The calendar of seminars can be found at: