Laboratoire d'informatique de l'École polytechnique

Talk by Jean-Éric Pin: «Dual space of a lattice as the completion of a Pervin space»

Speaker: Jean-Éric Pin (Irif)
Location: Room Grace Hopper, Alan Turing Building
Date: Fri, 30 Jun 2017, 11:00-12:00

Abstract: In this survey lecture, I will mainly cover well-known results from a new angle. A Pervin space is simply a set equipped with a lattice of subsets. This notion suffices to define a natural notion of completion which appears to be the dual of the original lattice. One can then show that any lattice of subsets can be described by a set of inequations of the form u <= v, where u and v are elements of its dual space. Applications to formal languages and complexity classes will be given.