For several years now, there has been a growing connection between automata and $\lambda$-calculus, in terms of syntax, semantics and logic.

The terms of the $\lambda$-calculus provide a natural generalisation of finite words and trees, while their semantics appears to be closely related to automata theory. Various works have been carried out to generalise to this higher-order framework the tools for the usual regular languages. The aim of this Lambda Pros day is to bring together researchers interested in these connections, in particular around topics such as

  • regular languages of $\lambda$-terms
  • higher-order automata and finitary semantics
  • specification logics, such as MSO
  • profinite spaces and Stone duality
  • higher-order model checking

and others. We hope that this Lambda Pros day will contribute to the convergence of these two communities of researchers working on automata theory and the syntax and semantics of the $\lambda$-calculus.

Attendance to the Lambda Pros day is open to everyone, but please register here for the meal provided by IRIF.

Organisers: Sam van Gool, Paul-André Melliès, Vincent Moreau.

Date: Wednesday 28 June 2023.

Localization: Room 146 of the Olympe de Gouge building.

Program of the day

This is a tentative program which may be subject to change. The slots for talks are of 35 minutes of presentation and 15 minutes of questions to encourage discussions between the participants, and questions during the talks are welcome.

9:30 → 10:20 · Sylvain Salvati · Recognizability and the simply typed lambda-calculus.

10:30 → 11:20 · Cécilia Pradic · Implicit streaming stream and tree transducers in the linear $\lambda$-calculus

11:30 → 12:20 · Noam Zeilberger · Generalizing and abstracting the notion of context-free language

12:15 → 14:00 · Lunch

14:00 → 14:50 · Denis Kuperberg · Cyclic Proofs, System T, and the Power of Contraction

15:00 → 15:50 · Tito Nguyen · Geometry of interaction meets actually existing automata: Temperley-Lieb algebras, attribute grammars and invisible pebbles

16:00 → 16:50 · Thomas Colcombet · Some half-baked non-standard thoughts on pros

17:00 → 17:30 · Vincent Moreau · Current challenges in profinite $\lambda$-terms