LambdaComb meeting, 11 January 2023

Information

The second meeting of the LambdaComb project will be held as a hybrid event at LIX, located in the Alan Turing building of Ecole Polytechnique, at the following address:

1 rue Honoré d'Estienne d'Orves, 91120 Palaiseau

Events will last roughly from 10:00-17:30 Paris time, and all talks and some of the discussions will be streamed live over BigBlueButton. The link to join is here.

Schedule

All talks will take place in Salle Henri Poincaré located on the ground floor of LIX. Lunch is at the Ecole Polytechnique cantine located in the "Grand Hall".

All times are CET.

Talk titles and abstracts

---

Cédric de Lacroix. Frobenius structure in star-autonomous categories. [slides]

It is known that the quantale of sup-preserving maps from a complete lattice to itself is a Frobenius quantale if and only if the lattice is completely distributive. Since completely distributive lattices are the nuclear objects in the autonomous category of complete lattices and sup-preserving maps, we study the above statement in a categorical setting. We introduce the notion of Frobenius structure in an arbitrary autonomous category, generalizing that of Frobenius quantale. We prove that the monoid of endomorphisms of a nuclear object has a Frobenius structure. If the environment category is star-autonomous and has epi-mono factorizations, a variant of this theorem allows to develop an abstract phase semantics and to generalise the previous statement. However, the converse – that in a star-autonomous category where the monoidal unit is a dualizing object, if the monoid of endomorphisms of an object has a Frobenius structure, then the object is nuclear – is not true in general. We give a counter-example to this conjecture and finally we argue that it holds if we add the condition that the monoidal unit embeds into this object as a retract.

---

Martin Pépin. Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs / Analyse asymptotique et génération aléatoire efficace de graphes dirigés ordonnés sans cycles [slides]

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70's by Robinson. In order to keep the density of such graphs under control, it is also useful to their number of edges into account too. However, the adaptation of Robinson's approach to achieve this goal (done by Gessel in the 90's) leads to counting formulas based on the inclusion-exclusion principle. This induces a high computational cost for the uniform random sampler based on this formula.

In this talk, I will introduce a new class of DAGs (DOAGs for Directed Ordered Acyclic Graphs), endowed with an independent ordering of the children of each vertex, offering a new modelisation tool. For this class we obtain a recursive decomposition scheme that is amenable to effective random sampling. We then show that our method also applies to classical DAGs, yielding an efficient random samper for them, and thus solving the aforementionned problem. I will finally present a first asymptotic result on DOAGs as well as an optimised random sampler for the case where the number of edges is not prescribed.

---

Les graphes dirigés sans cycles (ou DAGs pour “Directed Acyclic Graphs” en anglais) sont des graphes dirigés dans lesquels il n'y a aucun chemin d'arêtes d'un sommet vers lui même. Il s'agit d'une structure de données omniprésente en informatique dont le problème du comptage par nombre de sommets a été résolu par Robinson dans les années 1970. Afin de contrôler la densité de ces graphes, il est utile de fixer aussi leur d'arêtes. Cependant, l'approche de Robinson (étendue par Gessel dans les années 1990) amène à des formules de récurrence faisant apparaître le principe d'inclusion-exclusion, qui se prête mal à la génération aléatoire (efficace) par les méthodes classiques.

Dans cet exposé j'introduirai une nouvelle classe de DAGs (les DOAGs), enrichie avec un ordre sur les arêtes sortantes de chaque sommet, offrant un nouvel outil de modélisation. Pour cette classe nous obtenons une décomposition récursive amenant à des algorithmes de génération aléatoire efficaces. Je présenterai ensuite un premier résultat asymptotique ainsi qu'un générateur aléatoire optimisé pour le cas où le nombre d'arêtes est laissé libre.

---

Giulio Manzonetto. The Lambda Calculus - 40 Years Later [slides]

Barendregt's book "The Lambda Calculus, its syntax and semantics" (1981/84) has become a `classic' in Theoretical Computer Science because it presents the state of the art in lambda calculus in a comprehensive way, and proposes a number of open problems and conjectures. In 2022, Barendregt and Manzonetto published a `sequel' of this book, presenting the solutions of several of these problems, and more. In this talk, we will present a selection of these problems and the key ingredients that were employed to solve them.

---