Octobre 2013


Retour à la vue des calendrier
Mardi 1 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Etude de chaînes de Markov à l'aide de représentations de monoïdes
Description: Nicolas M. Thiéry Etude de chaînes de Markov à l'aide de représentations de monoïdesLa théorie des représentations des groupes finis est un sujetclassique. Dans le cadre plus général des monoïdes finis, la théorieest plus récente et a priori plus complexe. Cependant il existe desclasses de monoïdes où, comme pour les groupes, la théorie sesimplifie et fait surgir de la combinatoire, ce qui ouvre la porte àdes applications.Dans cet exposé, nous présenterons brièvement les éléments de lathéorie en mentionnant quelques développements algorithmiques récents[1], et décriront une application typique à l'étude d'une chaîne deMarkov sur des tas de sable à écoulement orienté [2]. La démarcheexploratoire sera illustrée par quelques calculs typiques avec lelogiciel Sage.Refs:- [1] Cartan invariant matrices for finite monoids http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dmAR0178- [2] arXiv:1305.1697: Directed nonabelian sandpile models on trees Ayyer, Schilling, Steinberg, T.
Mardi 8 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Normalité et automates
Description: Olivier Carton We strengthen the theorem that establishes that deterministic finitetransducers can not compress normal infinite words. We prove that, indeed,non-deterministic finite transducers, even augmented with a fixed number ofcounters, can not compress normal infinite words. However, there arepush-down non-deterministic transducers that can compress normal infinitewords. We also obtain new results on the preservation of normality withautomata selectors. Complementing Agafonov's theorem for prefix selectors,we show that suffix selectors also preserve normality. However, there aresimple two-sided selectors that do not preserve normality.
Vendredi 11 Octobre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Intensionnalité vs. extensionnalité : où est-elle la frontière ? (2e partie)
Description: Jean-Yves Moyen Au cours de ces trois séances de groupe de travail, je ferai le
"débriefing" de mon CRCT et je vous présenterai les résultats obtenus à
Nancy en collaboration avec Guillaume Bonfante et Pierre, ou à
Copenhague en collaboration avec James Avery et Jakob Simonsen (qui sera
par ailleurs prof invité chez nous en février).

Au gré de vos interruptions et de nos discussions, nous parlerons
sans doute de Rice et de Gödel, de cardinaux et de grands ordinaux,
d'ordre supérieur et de non déterminisme, de treillis, de partitions,
peut-être de topologie. Les catégoriciens pourront s'exercer à faire
commuter des diagrammes. Ne reniant pas mes origines, tout cela sera
enrobé dans une couche de complexité implicite.


Le point de départ est une relecture du théorème de Rice entamée
avec Pierre il y a quelques années. Au lieu de parler de "propriétés
extensionnelles", le résultat est vu comme parlant de l'équivalence
extensionnelle (p et q sont équivalents si ils calculent la même
fonction). Autrement dit, on quotiente l'ensemble des programmes par
leur extension.

Cette vision fait de Rice une équivalence parmi d'autres et on peut
chercher d'autres équivalences "intéressantes" entre programmes.
Notamment, l'ensemble des équivalences formant un treillis complet, on
peut étudier ce treillis.
Mardi 15 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Le rang d'une suite unimodale et fonctions theta partielles
Description: Jeremy Lovejoy Il existe des égalités inattendues autour du rang d'unesuite unimodale, telle que U(1,5,5n+3) = U(2,5,5n+3), où U(t,m,n) estle nombre de suites unimodales de poids n avec rang congru à t modulom. De telles égalités rappellent celles pour le rang d'une partitionqui ont été observées par F. Dyson et qui sont liées aux formesmodulaires et mock modulaires. Dans le cas des suites unimodales, iln'y a pas cette structure modulaire ; la démonstration dépend d'uneidentité de fonctions thêta partielles due à Ramanujan. Ceci est untravail en commun avec B. Kim (Séoul).
Vendredi 18 Octobre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Intensionnalité vs. extensionnalité : où est-elle la frontière ? (3e partie)
Description: Jean-Yves Moyen Au cours de ces trois séances de groupe de travail, je ferai le
"débriefing" de mon CRCT et je vous présenterai les résultats obtenus à
Nancy en collaboration avec Guillaume Bonfante et Pierre, ou à
Copenhague en collaboration avec James Avery et Jakob Simonsen (qui sera
par ailleurs prof invité chez nous en février).

Au gré de vos interruptions et de nos discussions, nous parlerons
sans doute de Rice et de Gödel, de cardinaux et de grands ordinaux,
d'ordre supérieur et de non déterminisme, de treillis, de partitions,
peut-être de topologie. Les catégoriciens pourront s'exercer à faire
commuter des diagrammes. Ne reniant pas mes origines, tout cela sera
enrobé dans une couche de complexité implicite.


Le point de départ est une relecture du théorème de Rice entamée
avec Pierre il y a quelques années. Au lieu de parler de "propriétés
extensionnelles", le résultat est vu comme parlant de l'équivalence
extensionnelle (p et q sont équivalents si ils calculent la même
fonction). Autrement dit, on quotiente l'ensemble des programmes par
leur extension.

Cette vision fait de Rice une équivalence parmi d'autres et on peut
chercher d'autres équivalences "intéressantes" entre programmes.
Notamment, l'ensemble des équivalences formant un treillis complet, on
peut étudier ce treillis.
Mardi 22 Octobre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Programmation linéaire colorée
Description: Pauline Sarrabezolles Considérons d + 1 ensembles de points de R^d en position
générique, et attribuons à chacun des ces ensembles une couleur
distincte. D'après le théorème de Carathéodory coloré, prouvé par Imre
Barany en 1982, si un point est contenu dans l'enveloppe convexe de
chacun de ces ensembles, alors il est contenu dans l'enveloppe convexe
d'un simplexe formé d'un point de chaque couleur. Un tel simplexe est
dit arc-en-ciel. La conjecture de la profondeur
simpliciale colorée, formulée par Antoine Deza et ses coauteurs en
2006, dit qu'un tel point est en fait contenu dans au moins d^2 + 1
simplexes arc-en-ciel, ce qui a été vérifié par différents auteurs
pour d = 1, 2 et 3. Nous vérifions cette conjecture en dimension 4 et
améliorons les bornes connues dans les dimensions plus élevées. Ces
résultats sont obtenus grâce à une généralisation combinatoire des
configurations colorées de points, suggérée par Imre Barany : les
systèmes octaédriques. Nous présentons de plus des algorithmes
résolvant divers problèmes de programmation linéaire colorée.
Vendredi 25 Octobre
Heure: 10:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques remarques d'ordre logique sur la théorie des types homotopiques (1ère partie)
Description: Christophe Fouqueré A partir du livre "Homotopy Type Theory", seront abordés les points
suivants: théorie des types (à la Martin-Löf), notions (très)
élémentaires d'homotopie et axiome d'univalence, hiérarchisation des
types et conséquences sur la partie interprétant la logique (en
particulier le tiers-exclus). Nous n'aborderons pas nombre de points
(théorie des catégories, types homotopiques d'ordre supérieur,
reconstruction des réels, ...) hautement intéressants de ce livre.
Mardi 29 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Random Boolean functions generated by random Boolean expressions
Description: Bernhard Gittenberger We will investigate the probability distribution on the set of Booleanfunctions in n variables if a Boolean function is generated by a largeBoolean expression drawn uniformly at random from all expressions ofthe same size. We show that a precise quantitative relation betweenthe probability of a function and its complexity which is defined asthe minimal size of an expression representing the function.