23 Février - 1 Mars


Retour à la vue des calendrier
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.