-
12 juin 2018 à 10h30, Salle 1
Simon Henry,
La conjecture de semi-strictification de Simpson
En 1991 M.Kapranov et V.Voevodsky ont publié un article sur
l'hypothèse d'homotopie affirmant que tout type d'homotopie peut être
représenté par un infini groupoïdes dont les lois de compositions,
d'unités et d'échanges sont strictes, et seule la loi d'inverse est
'faible' (i.e. seulement valide à 'isomorphisme' près).
En 1998 Carlos Simpson a montré que ce résultat est faux. Il a aussi
conjecturé que si on autorise les lois d'unités à être faibles alors le
résultat est vrai, et que cela se démontre probablement en utilisant la
méthode de Kapranov et Voevodsky.
Dans l'exposé je reviendrai sur l'article de Kapranov et Voevodsky, et
j'expliquerai précisément pourquoi il ne contient en fait pas une
preuve de cette conjecture et comment il faut modifier son approche pour
essayer de démontrer la conjecture.
Je donnerai deux formulations précises (à priori non équivalentes) de la
conjecture (dite "régulière" et "générale"). J'expliquerais pourquoi la
version "général" est hors de porté des méthodes de Kapranov et Voevodsky,
et je présenterai une preuve très récente de la version "régulière", qui
suit les idées de Kapranov et Voevodsky.
-
22 mai 2018 à 10h30, Salle 2
Frédéric Patras,
Structures algébriques sur les topologies finies et quasi-posets, II
Généralisant en partie des résultats sur les posets et diverses contructions topologiques classiques, on peut munir l'ensemble des topologies finies de structures algébriques "supérieures", naturellement liées à des objets combinatoires (en rapport avec les fonctions symétriques). Travaux avec L. Foissy et C. Malvenuto.
-
15 mai 2018 à 10h30, Salle 1
Frédéric Patras,
Structures algébriques sur les topologies finies et quasi-posets, I
Généralisant en partie des résultats sur les posets et diverses contructions topologiques classiques, on peut munir l'ensemble des topologies finies de structures algébriques "supérieures", naturellement liées à des objets combinatoires (en rapport avec les fonctions symétriques). Travaux avec L. Foissy et C. Malvenuto.
-
24 avril 2018 à 10h30, Salle 2
Étienne Lozes,
Buffered Simulation Games for Büchi Automata
Simulation relations are an important tool in automata theory because they provide efficiently computable approximations to language inclusion.
Simulations can be seen as turn-based games played between a « spoiler » that proposes chalenges and a « duplicator » that have to reply to these.
In recent years, extensions of ordinary simulations have been studied, for instance multi-pebble and multi-letter simulations, which yield better approximations and are still polynomial-time computable. The ideas behind these extensions is to let duplicator either « hide » his choices (for pebble games) or « delay » them (for multi-letter games).
In this talk, I will briefly recall these simulations, and then I will introduce a natural extension of multi-letter simulations called buffered simulations. Buffered simulations are based on a simulation game in which the two players share a FIFO buffer of unbounded size. I will introduce two variants of these buffered games called continuous and look-ahead simulation, which differ in how elements can be removed from the FIFO buffer. I will show that look-ahead simulation, the simpler one, is already PSPACE-hard, i.e. computationally as hard as language inclusion itself, whereas continuous simulation is even EXPTIME-hard. We also provided matching upper bounds for solving these games with infinite state spaces using some finite quotient games which I will briefly describe.
This is a joint work with Milka Hutagalung and Martin Lange: Arxiv preprint
-
20 avril 2018 à 11h00, Salle de Conférences
Célia Borlido,
Stone duality and the Substitution Principle, Part II
Since the pioneering work of Büchi in the 1960s, the study of regular languages and its connections to logic on words has been given a lot of attention by the theoretical computer science community, and a vast literature exists on the subject.
Logic on words also plays an important role in circuit complexity as many complexity classes admit characterizations in terms of logic fragments.
Fragments of logic defining regular languages can be studied inductively via the so-called "Substitution Principle”. Combined with profinite techniques, this approach has proved very successful, culminating e.g. in Almeida and Weil’s Basis Theorem.
However, in the setting of circuit complexity, many interesting logic fragments contain non-regular languages. Thus, classical profinite techniques no longer apply.
In this talk, I will interpret the "Substitution Principle" (for possibly non-regular languages) from the standpoint of Stone duality, and show how it can be used to obtain topo-algebraic counterparts for classes of languages defined by an arbitrary first-order logic fragment.
-
17 avril 2018 à 10h30, Salle 2
Nathan Grosshans,
The power of programs over monoids taken from some small varieties
of finite monoids
The computational model of programs over monoids, introduced by Barrington and Thérien in the late 1980s, gives a way to generalise the notion of (classical) recognition through morphisms into monoids in such a way that almost all open questions about the internal structure of the complexity class NC^1 can be reformulated as understanding what languages (and, in fact, even regular languages) can be program-recognised by monoids taken from some given variety of finite monoids. Unfortunately, for the moment, this finite semigroup theoretical approach did not help to prove any new result about the internal structure of NC^1 and, even worse, any attempt to reprove well-known results about this internal structure (like the fact that the language of words over the binary alphabet containing a number of 1s not divisible by some fixed integer greater than 1 is not in AC^0) using techniques stemming from algebraic automata theory failed.
In this talk, I shall present the model of programs over monoids, explain how it relates to "small" circuit complexity classes and present some of the modest contributions I made during my Ph.D. thesis to the understanding of the computational power of programs over monoids, focusing on the well-known varieties of finite monoids DA and J (giving rise to "small" circuit complexity classes well within AC^0).
-
13 avril 2018 à 11h00, Salle 1
Célia Borlido,
Stone duality and the Substitution Principle, Part I
Since the pioneering work of Büchi in the 1960s, the study of regular languages and its connections to logic on words has been given a lot of attention by the theoretical computer science community, and a vast literature exists on the subject.
Logic on words also plays an important role in circuit complexity as many complexity classes admit characterizations in terms of logic fragments.
Fragments of logic defining regular languages can be studied inductively via the so-called "Substitution Principle”. Combined with profinite techniques, this approach has proved very successful, culminating e.g. in Almeida and Weil’s Basis Theorem.
However, in the setting of circuit complexity, many interesting logic fragments contain non-regular languages. Thus, classical profinite techniques no longer apply.
In this talk, I will interpret the "Substitution Principle" (for possibly non-regular languages) from the standpoint of Stone duality, and show how it can be used to obtain topo-algebraic counterparts for classes of languages defined by an arbitrary first-order logic fragment.