-
24 juillet 2018 à 10h30
Mirna Dzamonja,
Foundations of Mathematics: what is new and what is old
We consider the interplay between the set-theoretic
and the homotopy-theoretic foundations of mathematics and show results
in mathematical logic which imply that modern mathematical foundations
need to be pluralists.
-
19 juin 2018 à 10h30, Salle 2
Étienne Lozes,
Procrastination in two-player games and continuous strategies
I will present the framework of regular infinite games with lookahead introduced Holtmann, Kaiser et Thomas [1].
A regular infinite game is a two player game where the objective of the second player is that the pair of infinite sequences of moves of the two players belong to some regular relation fixed in advance.
The variant game studied by Holtman, Kaiser, and Thomas is the one where the second player is allowed to « skip his turn » from time to time (but not co-finitely often).
It turns out that winning strategies in this setting correspond to continuous functions from the space of sequences of first players’ moves to the space of sequences of second player’s moves,
and that, in the specific setting studied by Holtman, Kaiser, and Thomas, these strategies are actually even Lipschitz fonctions. I will then come back to the buffered simulations and relate them to this framework. A notable difference is that the degree of lookahead needed for a buffered simulation cannot be bounded in advance, and that winning strategies in buffered simulations are continuous but not necessarily Lipschitz.
[1] Holtmann et al., "Degrees of Lookahead in Regular Infinite Games"
-
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.