Page du séminaire DUALL

DUALL seminar

This seminar is affiliated with the project Duall.


Thomas Colcombet, 16/05/2017 at 12:30PM, Irif, room 4033: Automata minimization and gluing of vector spaces II.

Daniela Petrişan, 10/05/2017, Irif: Automata minimization: a functorial approach and the minimization of subsequential transducers.

Daniela Petrişan, 03/05/2017, Irif: Automata minimization: a functorial approach.

In this talk we regard languages and their acceptors – such as deterministic or weighted automata, transducers, or monoids – as functors from input categories that specify the type of the languages and of the machines to categories that specify the type of outputs.

  1. We provide sufficient conditions on the output category so that minimization of the corresponding automata is guaranteed.
  2. We show how to lift adjunctions between the categories for output values to adjunctions between categories of automata.
  3. We show how this framework can be instantiated to unify several phenomena in automata theory, starting with determinization and minimization (which have been previously studied from a coalgebraic and duality theoretic perspective).
  4. We finally show how subsequential transducers can be seen as functors valued in a Kleisli category and explain Choffrut’s minimization algorithm.

Daniela Petrişan, 26/04/2017, Irif: Automata minimization and gluing of vector spaces I.

In this series of two talks, we will introduce a novel quantitative form of automata: “hybrid-set-vector automata”. These are joint generalizations of deterministic finite state automata and automata weighted over a field. These automata enjoy the existence of (algebraically) minimal recognizers for a function (i.e. series), while being (in some sense) more compact than automata weighted over a field.

The description of why these good minimal recognizers exist is properly explained at the level of categories. Hence, these talks will be the occasion to give an everview of the categorical reasons for minimizability, presenting:

  • a generic–yet not standard–presentation of automata using category theory, in which initial and final automata for a language are obtained by computing suitable left and right Kan extensions,
  • the importance of factorization systems for computing minimal automata, and how this notion can be refined to “factorization through systems”,
  • the notion of “gluing of categories”, which are special cases of free co-completions,
  • how in suitable cases, finite gluings of a category give rise to families of automata that are minimizable by design, and
  • the special motivating case of hybrid-set-vector automata which are automata in the category of finite gluings of finite vector spaces.

Luca Reggio, 19/04/2017, Irif: Quantifiers on languages and codensity monads II.

Luca Reggio, 24/03/2017, Irif: Quantifiers on languages and codensity monads I.

The main content of this talks concerns recent joint work with Mai Gehrke and Daniela Petrisan on the understanding, at the level of recognisers, of the effect of applying a layer of various kinds of quantifiers in the context of logic on words.

Two approaches have been remarkably effective in the study of languages: the algebraic one, and the logical one. Whereas the former relies on the notions of recognition by a monoid and of syntactic monoid of a language, the latter is based on a semantic on finite words. Since we are interested in possibly non-regular languages and it is known that, beyond the regular case, monoids do not provide a notion of recognition that is fine-grained enough to be useful, we work with the so-called Boolean spaces with internal monoids (BM for short) as recognising objects. Motivated by open problems on the separation of Boolean circuit complexity classes, where classes of languages are characterised in terms of logic fragments, given a BM recognising the language defined by a formula with a free first-order variable, we want to construct a BM recognising the language associated to the quantified formula (with respect to various kinds of quantifiers).

The main tools employed in our solution are duality theory and category theory, in particular the notion of the profinite monad associated to a monad on the category of sets and functions. In this setting, the profinite monad is a monad on the category of Boolean spaces (compact, Hausdorff and zero-dimensional spaces) and continuous maps that is defined using the standard category-theoretic notion of codensity monad of a functor. In the first part of the talk I will concentrate on the category-theoretic background needed in order to define profinite monads. In the second part, I will illustrate how this machinery, along with Stone duality for Boolean spaces, provide a solution to the problem at hand.

Jean-Éric Pin, 17/03/2017, Irif: Pervin spaces II.

Jean-Éric Pin, 08/03/2017, Irif: Pervin spaces I.

The original motivation of this lecture, as presented in Gehrke, Grigorieff, Pin (ICALP 10), was to compute the dual space of a lattice of subsets of some free monoid. According to Stone-Priestley duality, the dual space of a lattice can be identified with the set of its prime filters, but it is not always the simplest way to describe it. Consider for instance the Boolean algebra generated by the sets of the form uA*, where u is a word. Its dual space is equal to the completion of A* for the prefix metric and it can be easily identified with the set of finite or infinite words on A, a more intuitive description than prime filters.

Elaborating on this idea, one may wonder whether the dual space of a given lattice of subsets of a space can always be viewed as a completion of some sort. The appropriate setting for this question is a very special type of spaces, the so-called Pervin spaces, which form the topic of this lecture.

A Pervin space is a set X equipped with a set of subsets, called the blocks of the Pervin space. Blocks are closed under finite intersections and finite unions and hence form a lattice of subsets of X. Pervin spaces are thus easier to define than topological spaces or (quasi)-uniform spaces. As a consequence, most of the standard topological notions, like convergence and cluster points, specialisation order, filters and Cauchy filters, complete spaces and completion are much easier to define for Pervin spaces.

Michael Pinsker, 06/03/2017, Irif: New Topological Clones.

Every algebra carries, in addition to its algebraic structure, a natural topological structure: this structure is given by the topology of pointwise convergence on its term functions. Topological clones are the abstract algebraic and topological objects which capture both the algebraic and topological structure of algebras, similarly to topological groups which appear as the algebraic and topological abstraction of permutation groups. In my lecture I am going to explain what we can tell about an algebra from its topological clone. This will lead me in particular into complexity theory, where certain computational problems, called Constraint Satisfaction Problems, are investigated systematically via their polymorphism algebras, and subsequently via topological clones. Finally, I will show how the algebraic modelling of function clones can be altered in order to be more suitable for constraint satisfaction.

Urbat Henning, 08/09/2016, Room 4033: Unary presentations of monads.

Howard Straubing, 23/05/2016, Irif: Derived categories.

Thomas Colcombet, 11/02/2016, Irif: Regular Cost Functions 2.

Thomas Colcombet, 28/01/2016, Irif: Regular Cost Functions I.

Célia Borlido, 27/01/2016, Irif: The word problem and some reducibility properties for pseudovarieties of the form DRH.

Luca Reggio, 14/01/2016, Irif: Schneider, Zumbragel: Profinite algebras and affine boundedness.

Daniela Petrişan, 10/12/2015, Room 3052: Standard topological algebras: syntactic and principal congruences and profiniteness II.

Daniela Petrişan, 03/12/2015, Room 3052: Standard topological algebras: syntactic and principal congruences and profiniteness I.

A presentation of the paper of David M. Clark, Brian A. Davey, Ralph S. Freese, and Marcel Jackson (]).

Sam van Gool, 19/11/2015, Irif: Monadic second order logic as the model companion of modal logic.

(joint work with Silvio Ghilardi)

We exhibit a connection between monadic second order logics and modal logics, making use of the language of first-order model theory; specifically, model companions. Model companions stem from A. Robinson’s work on model completions: a model companion of a universal theory T is an extension T* of T which has the same universal consequences (i.e., T* is a co-theory of T), but in addition allows for the elimination of quantifier alternations (i.e., T* is model-complete). Monadic second order logic and modal logic are two different formalisms that can be used to describe the same classes of models, such as infinite words, or infinite trees. Both logics, when interpreted in appropriate power set structures, can actually be viewed as first-order theories. We show in several specific cases that the first-order theory corresponding to MSO is the model companion of the first-order theory corresponding to modal logic. During the talk, I will focus on MSO on infinite words, and show how it can be characterized as the model companion of linear temporal logic with an initial element.

Reference: Ghilardi and van Gool, “A model-theoretic characterization of monadic second order logic on infinite words”, ??.

Daniela Petrişan, 02/12/2015, Irif: ProfineV=StoneV?.

Reading group on the Clark et al paper on the question whether profiniteV=StoneV?\~ralph/Preprints/stasc.pdf