Février 2015


Retour à la vue des calendrier
Mardi 3 Février
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Graph polynomials and relations with physics
Description: Adrian Tanasa In the first part of the talk I will introduce the Tuttepolynomial of graphs and explicitly show its relation withpolynomials appearing in the so-called parametric representation ofintegrands canonically associated to graphs in quantum field theory.In the second part of the talk I will show a new proof of thecelebrated property of universality of the Tutte polynomial of graphs(or matroids), proof which does not require the usual edge inductionarguments. Finally, I will present how this proof generalizes for theuniversality property of the Bollobas-Riordan polynomial of ribbongraphs (or embedded graphs).
Mardi 10 Février
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Énumérer les cartes farcies de toute topologie (avec un soupçon de combinatoire analytique)
Description: Gaëtan Borot Les cartes sont des surfaces discrètes construites en recollant lelong de leurs bords des polygônes - l'exemple le plus simple étant lestriangulations. En tant que surfaces orientables, leur topologie estcaractérisée par le nombre de bords n, et le nombre d'anses g. Si l'onse donne un poids de Boltzmann t_k pour chaque k-gone, l'énumérationdes cartes à un bord et de genre 0 est un problème très bien étudié.Ici, je considèrerai le problème plus général d'énumérer les cartesfarcies: ce sont les surfaces obtenues en a) piochant dans une boîte àoutils pouvant contenir des surfaces à bords polygonaux et detopologie quelconque ; b) en recollant ces morceaux élémentaires lelong de leurs bords ; c) pondérant l'énumération par des poids deBoltzmann dépendant du genre et de la longueur des bords de chaquemorceau élémentaire. J'expliquerai notamment qu'il existe unerécurrence universelle sur la caractéristique d'Euler totale 2 - 2g -n, qui réduit le problème d'énumération en toute topologie à celui desdisques (n = 1, g = 0) et des cylindres (n = 2,g = 0).
Vendredi 13 Février
Heure: 11:30 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Model checking en logique de dépendance
Description: Nicolas de Rugy-Altherre La logique de dépendance et ses variantes (indépendance et inclusion) ont été introduites par Vänäänen il y a quelques années pour parler de façon "propre" de dépendance en logique. Je présenterai cette logique et ses résultats principaux en complexité.
Mardi 17 Février
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Problèmes de satisfaction de contraintes et graphes inhomogènes
Description: Élie de Panafieu
Jeudi 19 Février
Heure: 16:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Modelling Timed Concurrent Systems Using Activity Diagram Patterns
Description: Étienne André UML is the de facto standard for modelling concurrent systems in the industry.
Activity diagrams allow designers to model workflows or business processes.
Unfortunately, their informal semantics prevents the use of automated verification techniques.
In this paper,
we first propose activity diagram patterns for modelling timed concurrent systems;
we then devise a modular mechanism to compose timed diagram fragments into a UML activity diagram that also allows for refinement, and
we formalise the semantics of our patterns using time Petri nets.
Our approach guides the modeller task% (helping to avoid common mistakes), and allows for automated verification.

Joint work with Christine Choppy and Thierry Noulamo
Vendredi 20 Février
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Coherence spaces for computable analysis
Description: Kazushige Terui Abstract:
There have been two mainstream approaches in
computable analysis: the type-two theory of effectivity (TTE)
and the theory of domain representations. This paper proposes
an intermediary approach based on coherence spaces, which is
as concrete as TTE and as structured as domain theory.

We import various concepts from TTE such as admissibility,
and provide admissible representations for the real line, Euclidean
spaces and function spaces over them. This allows us
to represent, for instance, a real continuous function by a stable
map. A natural question is then what linear maps correspond
to in terms of analysis. Our answer is that they correspond
to uniformly continuous functions. This leads to an internal
expression of Heine's theorem (every continuous function on a
compact interval of the real line is uniformly continuous) as the
existence of a certain map from a stable function space to a linear
function space.

We finally illustrate an application of coherence spaces as a
type system for lambda calculus, which allows us to verify local
properties of real functions.

This is a joint work with Kei Matsumoto.
Mardi 24 Février
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Profile of random trees
Description: Michael Drmota
Mercredi 25 Février
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quasi-random properties of subsequences of sequences generated by finite automata
Description: Michael Drmota Automatic sequences T(n) are the output sequence of a finite automaton, wherethe input is the q-adic digital representation of n. The most prominent exampleis the Thue-Morse sequence t(n) (that is also the fixed point of the substitution0 -> 01, 1 -> 10). Automatic sequences have been studied in many diff erent contextsfrom combinatorics to algebra, number theory, harmonic analysis, geometryand dynamical systems. For example, they have a linear subword complexity andthey are almost periodic.Since the subword complexity is linear the entropy of the related dynamical system is zero. This also means thatthey do not behave like a random sequence. However, the situation changes drastically whenone uses proper subsequences of automatic sequences, for example the subsequence along primes orsquares. It is conjectured that the resulting sequences are normal sequences so thatthey behave like random sequences (=quasi random sequences).Recently this property was proved (together with C. Mauduit and J. Rivat)for the Thue-Morse sequence along the subsequence of squares - and it turns out that thispropery extends to several other automatic sequences and also to subsequences of the form[n^c], where 1 < c < 4/3. Thus such subsequences of automatic sequences give rise toa completely new class of pseudo random sequences that can be computed very efficiently.
Heure: 14:00 - 15:00
Lieu: Amphi A
Résumé: Quasi-Random Properties of Subsequences of Sequences Generated by Finite Automata
Description: Michael Drmota Automatic sequences T(n) are the output sequence of a finite automaton, where
the input is the q-adic digital representation of n. The most prominent example
is the Thue-Morse sequence t(n) (that is also the fixed point of the substitution
0 -> 01, 1 -> 10). Automatic sequences have been studied in many diff erent contexts
from combinatorics to algebra, number theory, harmonic analysis, geometry
and dynamical systems. For example, they have a linear subword complexity and
they are almost periodic.

Since the subword complexity is linear the entropy of the related dynamical system is zero. This also means that
they do not behave like a random sequence. However, the situation changes drastically when
one uses proper subsequences of automatic sequences, for example the subsequence along primes or
squares. It is conjectured that the resulting sequences are normal sequences so that
they behave like random sequences (=quasi random sequences).
Recently this property was proved (together with C. Mauduit and J. Rivat)
for the Thue-Morse sequence along the subsequence of squares - and it turns out that this
propery extends to several other automatic sequences and also to subsequences of the form
[n^c], where 1 < c < 4/3. Thus such subsequences of automatic sequences give rise to
a completely new class of pseudo random sequences that can be computed very efficiently.
Vendredi 27 Février
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Linear numeral systems
Description: Ian Mackie We take a fresh look at an old problem of representing natural numbers
in the lambda-calculus. Our interest is in finding representations
where we can compute efficiently (and where possible, in constant
time) the following functions: successor, predecessor, addition,
subtraction and test for zero. Surprisingly, we find a solution in the
linear lambda-calculus, where copying and erasing are not permitted.