École Jeunes Chercheurs du GDR Informatique Mathématique

	Lundi	Mardi	Mercredi	Jeudi	Vendredi
8h30	Modélisation géométrique Cédric Gérot (GIPSA-Lab, Grenoble)	The p-adic ergodic theory and applications Vladimir Anashin (Université de Moscou)	Calculabilité sur les entiers et les réels Laurent Bienvenu (CNRS, LIAFA)	Combinatoire des mots et algorithmique du texte Florence Levé (MIS, UPJV)	Systèmes dynamiques Samuel Petite (LAMFA, UPJV)
9h
9h30
Combinatoire des mots et algorithmique du texte Richard Groult (MIS, UPJV)
10h
10h30	Pause Café	Pausé Café	Pause Café	Pause Café
11h	Modélisation géométrique Bruno Lévy (INRIA, Nancy)	The p-adic ergodic theory and applications Vladimir Anashin (Université de Moscou)	Calculabilité sur les entiers et les réels Mathieu Hoyrup (INRIA, Nancy)	Pause Café	Systèmes dynamiques Fabien Durand (LAMFA, UPJV)
11h30	Combinatoire des mots et algorithmique du texte Arnaud Lefebvre (LITIS, Rouen)
12h	The p-adic ergodic theory and applications Ai Hua Fan (LAMFA, UPJV)
12h30
13h	Pause repas	Pause repas	Pause repas	Pause repas	Pause repas
13h30
14h	Wang BaoWei : Interactions of arithmetic and metric properties in beta expansion.
Maniatakos Fivos : Multi Factor Graph - une nouvelle structure pour l’alignement de séquences. Applications à la musique.
14h30	Abdmouleh Fatma : Reconstruction de Q-convexes discrets pour des sources ponctuelles	Deneufchâtel Matthieu : Indépendance des hyperlogarithmes	Grenet Bruno : Déterminant vs Permanent.	Jolivet Timo : Systèmes dynamiques du point de vue combinatoire.
Leroy Julien : Conjecture S-adique : cas général et complexité 2n.
15h	Collet Gwendal : Combinatoire bijection des cartes		Cano Guillaume : La Formalisation des Mathématiques en Coq.	Boyer Laurent : Comportements typiques dans les automates cellulaires.
Brigitte Vallée. Présentation du GDR IM
15h30	Mailler Cécile : Le modèle des arbres croissants pour la représentation de fonctions booléennes aléatoires.	Visite guidée de la cathédrale	Briquel Irénée : Recherche de racines approchées de polynômes : une méthode par homotopie.	Marcovici Irène : Autour des automates cellulaires probabilistes.
16h	Pause Café	Pausé Café	Pause Café	Perrot Kevin : Kadanoff Sand Pile Models.
16h30	Roux Mathieu : Théorie de l'information: sources, séries de Dirichlet, analyse réaliste d'algorithmes.	Langer Robin : Symmetric functions and Macdonald polynomials	Vandomme Élise : Complexité syntaxique d’ensembles d’entiers ultimement périodiques.	Clôture
17h	Belhaj Skander : Calcul rapide sur les matrices de Hankel.	Dahmoune Mohamed : Transition reduction of automata.	Vanier Pascal : Ensembles $\pi^0_1$ et pavages.
17h30			Giambruno Laura : Transducteurs pour le décodage bilatère des codes préfixes.	Chandesris Jérôme : Une évolution des Automates cellulaires pour simuler les réactions biologiques compartimentées.

18h	Pot d'accueil
	19h Banquet

Détail des cours :

Cédric Gérot, Bruno Lévy
Modélisation géométrique

Résumé : Dans ce cours nous parlerons de deux ponts qui relient les objets discrets que sont les maillages surfaciques aux objets continus que sont les surfaces paramétrées : les schémas de subdivision et la paramétrisation des surfaces triangulées.
Dans un premier temps nous explorerons les schémas de subdivision en nous attachant à deux aspects essentiels qui les caractérisent : d'une part ce sont des outils qui construisent un lien entre le discret (maillages) et le continu (variété), et d'autre part ils généralisent les Box-splines à des polyèdres de contrôle de connectivité irrégulière. Ces deux propriétés en font un outil privilégié pour dessiner efficacement une courbe ou une surface continue sur un écran discret, mais également pour être la prédiction dans la modélisation d'une transformée en ondelettes de deuxième génération. Au fil de ce cours nous donnerons les résultats essentiels concernant cet outil, des recettes pour construire soi-même un schéma de subdivision ayant de bonnes propriétés, et des références aux travaux les plus récents de ce domaine.
Dans un deuxième temps, nous traiterons de la paramétrisation des surfaces triangulées. Après un rappel des notions de géométrie différentielle qui constituent les briques de base de ce sujet, nous présenterons la paramétrisation de surfaces simples (disques topologiques), avant d'évoquer la paramétrisation plus générale de surfaces de genre arbitraire et de surfaces fermées. Ces résultats seront illustrés par diverses applications. Nous nous pencherons alors en particulier sur les méthodes numériques utilisées pour la paramétrisation des surfaces triangulées : résolution de systèmes linéaires par méthodes itératives ou directes, optimisation de fonctions, ou encore optimisation contrainte. Quelques pointeurs vers des implantations disponibles sur internet seront alors proposés.
Revenir au programme
Vladimir Anashin, Ai Hua Fan
Title: The p-adic ergodic theory and applications
Lecture 1: Basics of p-adics
- p-adic numbers
- p-adic distance
- p-adic Calculus
Lecture 2: The p-adic ergodic theory
- Basics
- Ergodic transformations on the space of p-adic integers
- Ergodic transformations on p-adic balls and p-adic spheres
Lecture 3: Applications
- Latin squares
- Pseudo random generators and stream ciphers
- Transducers
Lecture 4: Two classes of dynamics
- Shifts and chaotic systems
- Odometers and minimal systems
Revenir au programme
Laurent Bienvenu, Mathieu Hoyrup
Titre : Calculabilité sur les entiers et les réels

Résumé : Ce cours constituera une brève introduction à la théorie de la calculabilité. Cette théorie s'intéresse à la frontière entre ce qui est algorithmiquement calculable et ce qui ne l'est pas. Le cours comportera deux parties.
La première présentera les bases de la calculabilité pour les objets finis discrets (entiers, chaînes de caractères, etc.) : machines de Turing, notions d'ensemble et de fonction calculable, d'ensemble récursivement énumérable, problème de l'arrêt et son incalculabilité. On y verra également des concepts plus avancés comme celui d'oracle, de relativisation et de réduction Turing, ainsi que quelques théorèmes fondateurs du domaine, comme le théorème de Matiyasevitch sur les ensembles diophantiens, ou le théorème de Freidberg-Muchnik concernant l'existence d'un degré intermédiaire entre les ensembles calculables et le problème de l'arrêt.
Dans la seconde partie du cours nous verrons que cette théorie peut s'étendre des objets finis, discrets aux objets infinis, continus. Nous aborderons ainsi les notions de réel calculable, de fonction réelle calculable, d'ensemble calculable de réels. La notion de fonction réelle calculable peut se définir de deux manières, par machine de Turing classique ou par celle plus évoluée de machine à oracle : nous présenterons le théorème de Kreisel-Lacombe-Shoenfield, qui permet de relier ces deux modèles. Quelques illustrations des concepts abordées seront aussi données, comme la calculabilité de l'ensemble de Mandelbrot, des ensembles de Julia.
Revenir au programme
Richard Groult, Arnaud Lefebvre, Florence Levé
Titre : Combinatoire des mots et algorithmique du texte
I. Mots et morphismes (Florence Levé)
II. Mots et tableaux
a. Des mots aux tableaux (Richard Groult)
b. Mais à qui est ce tableau ? (Arnaud Lefebvre)

Résumé : Dans ce cours, nous parlerons de la recherche de propriétés sur les mots finis et infinis.
La première partie sera une introduction à la combinatoire des mots et des morphismes. Nous commencerons par présenter des généralités sur les mots finis et infinis, ainsi que des résultats classiques sur des mots "célèbres" (mot de Thue-Morse, mot de Fibonacci…). Nous expliquerons ensuite comment les morphismes peuvent intervenir dans la recherche de propriétés sur les mots infinis, en détaillant comme exemple la recherche de quasipériodicité dans les mots sturmiens et épisturmiens.
La deuxième partie sera consacrée à des algorithmes sur les mots finis. De nombreux tableaux d'entiers permettent de stocker des propriétés sur les mots comme, par exemple, la table des suffixes qui représente l'ordre lexicographique de tous les suffixes d'un mot, ou encore, le tableau de bords qui contient la longueur du plus long bord de chaque préfixe d'un mot. Dans un premier temps nous présenterons différents tableaux et algorithmes permettant de les générer ainsi que des exemples d'utilisations. Puis dans un second temps nous nous demanderons si un tableau d'entiers donné peut être un de ces tableaux, et si oui, à quel(s) mot(s) correspond-il et avec quelles contraintes sur la taille de l'alphabet ?
Revenir au programme
Samuel Petite, Fabien Durand
Titre : Systèmes dynamiques
Première partie : Introduction à la dynamique symbolique en grande dimension.
Résumé : Il s'agit d'une introduction à la dynamique symbolique en dimension 2 (voire plus grande), où nous présentons comment l'étude des systèmes dynamiques permet de donner des propriétés combinatoires de ces systèmes, et inversement comment la combinatoire produit des exemples intéressants en dynamique.
Plus précisément, nous expliciterons les propriétés de base de sous-shifts de type fini et des substitutions symboliques. Nous montrerons alors qu'il existe des différences fondamentales avec la dynamique symbolique de dimension 1.
Deuxième partie : Utilisation des systèmes dynamiques dans des problèmes combinatoires.
Résumé : Dans ce cours nous allons détailler les preuves de deux théorèmes : Le théorème de van der Waerden (1927) et le Théorème de Cobham (1969). Ces résultats ont plusieurs points communs. Ils sont de nature arithmético-combinatoire. Les premières preuves qui en furent données étaient combinatoires. Par la suite d’autres preuves ont été trouvées. A plus d’un égard, les plus satisfaisantes sont de nature ”dynamiques” : un codage du problème permet de se ramener à l'étude du décalage sur un ensemble de suites bien choisi. (Énoncé des théorèmes)
Revenir au programme

Exposés.

Abdmouleh Fatma (LSIIT, Université de Strasbourg)
Titre : Reconstruction de Q-convexes discrets pour des sources ponctuelles.
Résumé : L'exposé présente une classe d'ensembles dits Q-convexes. La reconstruction de ces ensembles à partir de leurs projections par des sources ponctuelles est ensuite expliquée.
Belhaj Skander (Université de Tunis & Université de Jendouba)
Titre : Calcul rapide sur les matrices de Hankel.
Résumé : Dans cet exposé, nous présentons une contribution à l’amélioration de certains résultats concernant les algorithmes en algèbre matricielle et plus particulièrement les algorithmes sur les matrices de Hankel. Nous introduisons un algorithme efficace de diagonalisation par blocs approchée des matrices de Hankel. Cette diagonalisation par blocs approchée nous génère la suite des restes et la suite des quotients apparues au cours de l’exécution de l’algorithme d’Euclide. Des comparaisons numériques montrent l’efficacité de notre approche.
Boyer Laurent (LAMA, Université de Savoie)
Titre : Comportements typiques dans les automates cellulaires.
Résumé : à venir
Briquel Irénée (LIP, ENS Lyon)
Titre : Recherche de racines approchées de polynômes : une méthode par homotopie.
Résumé : Le problème connu sous le nom de 17e problème de Smale s'intéresse à la recherche de racines approchées de systèmes de n polynômes complexes à n inconnues. Dans sa liste de problèmes pour le 21e siècle, Steve Smale se demandait si il existait un algorithme retournant une racine approchée et fonctionnant en temps polynomial en moyenne, pour un système aléatoire. Beltran et Pardo ont proposé un algorithme probabiliste, dont l'espérance du temps de calcul est polynomial en moyenne pour ce problème. Toute l'étude de ce problème était faite en arithmétique exacte, en réalisant des opérations arithmétques avec précision infinie. Nous nous avons étudié les questions de précision, précédemment ignorées, et avons établi que cet algorithme probabiliste pouvait être adapté en précision finie, et que l'espérance du nombre de bits nécessaire est elle aussi polynomiale.
Cano Guillaume (INRIA, Nice Sophia Antipolis)
Titre : La Formalisation des Mathématiques en Coq.
Résumé : Formaliser des mathématiques c'est écrire des preuves mathématiques dans un certain langage de programmation (ici Coq) pour qu'elles puissent être vérifiées formellement par un ordinateur. Une première partie de l'exposé portera sur les motivations d'un tel travail. Une question qu'on pourrait ce poser est : comment être sûr que l'ordinateur ne fait aucune erreur lors des vérifications ? La réponse à cette question fera l'objet de la deuxième partie de l'exposé en expliquant un peu le fonctionnement du logiciel Coq.
Chandesris Jérôme (I3S, Nice Sophia Antipolis)
Titre : Une évolution des Automates cellulaire pour simuler les réactions biologiques comparimentées.
Résumé : Les automates cellulaires introduit par Conway en 1970 permettent l'analyse de certaine phénomène du vivant. Le jeu de la vie est un des exemples les plus connus. Mais de nombreuses autres applications de ce modèle de calcul sont utilisées tous les jours dans la vie courante. Certains phénomènes comme la diffusion des pigments des cellules de la peau des vaches, ont nécessités une évolution de la définition originale des automates cellulaires. Depuis, d'autres variantes de ce modèle ont été définies afin de pouvoir étudier de nombreux comportements. Une nouvelle variante pousse la définition du domaine discret au domaine continu. Cette définition permet de prendre en compte de nouvelles contraintes biologiques qui sont aux coeurs des études biologiques actuelles. La dynamique, la convergence, la densité, l'évolution d'une soupe organique dense sont les propriétés qui peuvent être connues grâce à ce modèle. L'analyse des diverses réactions issu d'un réseau métabolique ou génétique peut ainsi être étudié en considérant les différents compartiments d'une cellule. L'avantage du continu par rapport aux discret est la possibilité de représenter les particules de tailles diverses à des positions quelconque de l'espace 3D. L'agencement de ces particules permet de représenter les complexes de façon précise au besoin. La création temporaire de complexe ou de pseudo complexe intervenant dans les réactions, fait parti des informations que ce modèle permet de découvrir. Ainsi que la possibilité d'étudier le comportement d'une nouvelle molécule, sans devoir utiliser un protocole couteux en matériels et lent, parmi un réseau biologique en prenant en compte sa concentration, sa position dans la cellule, ... .
Collet Gwendal (LIX, École Polytechnique)
Titre : Combinatoire bijective des cartes.
Résumé : Les cartes sont des graphes plongés sur une surface. Les outils de la combinatoire bijective et de l'analyse complexe permettent de comprendre la structure de ces objets et ainsi de les compter, d’étudier leurs statistiques. On s’intéressera en particulier à certaines classes de cartes comme les cartes biparties, dont on donnera des formules d’énumération explicites.
Dahmoune Mohamed (LACL, Université Paris Est)
Titre : Transition reduction of automata.
Résumé : We are interested in the problem of transition-reduction of non-deterministic automata. We present some results on the reduction of the automata recognizing the language $L_n$ denoted by the regular expression $E_n=(a_1+\varepsilon)\cdot (a_2+\varepsilon)\cdot (a_3+\varepsilon)\cdots (a_n+\varepsilon)$. These results are used in the general case of the transition-reduction problem.
Deneufchâtel Matthieu (LIPN, Université Paris 13)
Titre : Indépendance des hyperlogarithmes.
Résumé : Dans cet exposé, je présente différents outils qui permettent de prouver des propriétés d'indépendance linéaire des hyperlogarithmes sur certains corps de fonctions. L'histoire commence par l'algèbre d'un monoïde que l'on considère dans le cas où l'anneau est une algèbre différentielle. Ensuite, on fait apparaître une équation différentielle dont les solutions sous forme de séries ont des propriétés d'indépendance des coefficients. Or les intégrales itérées qui définissent les hyperlogarithmes sont liées à cette équation ce qui permet de conclure sur l'indépendance linéaire des hyperlogarithmes.
Giambruno Laura (LIPN, Paris 13)
Titre : Transducteurs pour le décodage bilatère des codes préfixes
Résumé : Dans cet exposé, on définit un transducteur bi-déterministe pour le décodage bidirectionnel de mots codés par la méthode introduite par Girod (basée sur les codes préfixes). On introduit également une variante de la méthode de Girod, et on définit un transducteur qui permet le décodage de droite à gauche et de gauche à droite. Il est prouvé que ce transducteur est minimal. On considère le nombre d'états d'un tel transducteur, lié à certaines caractéristiques du code préfixe X considéré. On trouve quelques bornes pour le nombre d'états en relation avec les différentes notions de "taille" de X. En particulier on obtient une formule exacte pour les codes préfixes maximaux et on présente deux familles de codes préfixes représentant les cas extrêmes.
Grenet Bruno (LIP, ENS Lyon)
Titre : Déterminant vs Permanent.
Résumé : La question centrale bien connue de la théorie de la complexité est la question P vs NP, qui peut se traduire par « Est-il plus facile de vérifier une solution que d'en trouver une ? » Parmi les nombreuses approches pour tenter de répondre à cette question se trouve la complexité algébrique : au lieu de travailler sur des problèmes booléens, la complexité algébrique étudie des problèmes venant de l'algèbre linéaire comme par exemple la complexité du calcul du déterminant. Dans mon exposé, je présenterai la question Déterminant vs Permanent qui peut être vue comme la traduction de la question P vs NP dans le cadre algébrique. Je montrerai également le genre de question concrète sur lesquelles on peut travailler quand on s'intéresse à ce problème extremement difficile.
Jolivet Timo (LIAFA/FUNDIM, Université Paris 7 & Université de Turku, Finlande)
Titre : Systèmes dynamiques du point de vue combinatoire.
Résumé : Nous illustrons par des exemples comment la dynamique de certains systèmes a priori compliqués peut être réduite à des objets combinatoires simples tels que les sous-shifts de type fini ou substitutifs.
Langer Robin (LIAFA, Université Paris 7)
Titre : Symmetric functions and Macdonald polynomials.
Résumé : Introduction aux polynômes symétriques et polynômes de Macdonald pour ceux qui ne les ont jamais étudiés.
Leroy Julien (LAMFA, Université de Picardie Jules Verne)
Titre : Conjecture S-adique : cas général et complexité 2n.
Résumé : La conjecture S-adique stipule l'existence d'une condition C telle qu'une suite sur un alphabet fini est de complexité sous-affine si et seulement si elle est S-adique satisfaisant la condition C. Certains sous-cas sont déjà connus, mais le cas général reste incomplet. Dans cet exposé, nous exposons quelques améliorations d'un résultat de Ferenczi permettant d'obtenir une déocmposition S-adique à partir des graphes de Rauzy. Nous annonçons également un résultat donnant une caractérisation S-adique des suites dont la différence première de complexité est majorée par 2.
Mailler Cécile (Laboratoire de Mathématiques de Versailles, Universié de Versailles Saint Quentin)
Titre : Le modèle des arbres croissants pour la représentation de fonctions booléennes aléatoires.
Résumé : On définit, via leur représentation arborescente, une loi de probabilité sur l'ensemble des fonctions Booléennes à k variables. Cette nouvelle loi, que l'on nomme loi des arbres croissants, est inspirée du modèle de croissance des arbres binaires de recherche. On l'étudie dans différents systèmes logiques et on la compare à des distributions déjà étudiées : celle des arbres de Catalan, celle des arbres de Galton-Watson, et celle des arbres équilibrés.
Maniatakos Fivos (IRCAM)
Titre : Multi Factor Graph - une nouvelle structure pour l’alignement de séquences. Applications à la musique.
Résumé : Dans cet exposé on présentera une nouvelle structure informatique pour la représentation des données multi-flux sous le nom MFG (Multi Factor Graph). Inspirée par les avancées de la théorie des graphes et l'indexation automatique à l'aide des automates, MFG est à la base une nouvelle structure informatique-automat pour l'alignement des séquences, et elle a été conçue pour pour la synthèse sous contraintes à partir du contenu. MFG permet l'apprentissage de flux simultanés, leur représentation numérique en occupant des ressources de calcul réduites, et la régénération des flux stylistiquement cohérents avec ceux appris sous des critères externes exprimés par des contraintes. Le travail mené autour de MFG inclut les formalismes pour sa définition, un algorithme pour sa création et sa mise un jour dynamique, ainsi que des algorithmes pour un ensemble des différents types des requêtes primitives. Ces primitives peuvent être classifiées en deux catégories de problèmes, celui d'indexation et celui de scheduling de séquences. A travers une approche bottom-up, la combinaison diverse des algorithmes conçus pour ces primitives peut répondre à plusieurs problèmes complexes de haut niveau rencontrés dans le domaine de la création artistique par le contenu.
Marcovici Irène (LIAFA, Université Paris 7)
Titre : Autour des automates cellulaires probabilistes.
Résumé : Les automates cellulaires déterministes (AC) sont des systèmes dynamiques pour lesquels le temps et l'espace sont discrets. Un AC est constitué d'un réseau de cellules qui contiennent chacune une lettre d'un alphabet fini. Les contenus des cellules évoluent de manière synchrone et uniforme en fonction des états d'un nombre fini de leurs voisines. Les automates cellulaires probabilistes (ACP) sont une extension des AC permettant de prendre en compte des événements aléatoires : à chaque pas de temps, le nouveau contenu de chaque cellule est choisi aléatoirement et indépendamment des autres, selon une distribution dépendant seulement d'un nombre fini de cellules voisines. Nous nous intéressons au comportement asymptotique des ACP. Un ACP peut être vu comme une chaîne de Markov, la recherche d'états d'équilibre correspond donc à l'étude des mesures invariantes de cette chaîne de Markov. Après avoir présenté quelques résultats généraux relatifs aux ACP ergodiques, nous nous intéresserons à un exemple particulier d'ACP, correspondant à la règle majorité.
Perrot Kevin (LIP, ENS Lyon)
Titre : Kadanoff Sand Pile Models.
Résumé : Sand Pile Models are dynamical systems describing the evolution from N stacked grains to a stable configuration. The main interest of Sand piles relies in their self-organized criticality, the property that a small perturbation has uncontrolled consequences on the system. I will present a new tool used to handle this complex behaviour, transducers.
Roux Mathieu (Greyc, LMNO, UCBN)
Titre : Théorie de l'information: sources, séries de Dirichlet, analyse réaliste d'algorithmes.
Résumé : Les analyses classiques des algorithmes de tri et de sélection (par exemple QuickSort ou QuickSelect), considèrent le nombre de comparaisons entre clés. Ici, on se pose une question plus réaliste dans deux directions: on considère le nombre total de comparaisons entre symboles des mots qui constituent ces clés, quand ces clés sont issues d'une source générale sur un alphabet $\Sigma$. L'analyse fait alors intervenir la série génératrice (de type Dirichlet) des probabilités $p_w$ qu'un mot commence par un préfixe $w$, $$\Lambda(s)=\sum_{w\in\Sigma^*} p_w^ s, $$ qui admet (le plus souvent en pratique) une singularité en $s = 1$. Il est alors crucial pour l'analyse de ces algorithmes de pouvoir situer les autres pôles de $\Lambda$: y'en a-t-il d'autres sur la droite verticale $\{\Re(s)=1\}$? et quelle est la forme d'une zone à gauche de cette droite, où il n'y a pas d'autre pôles et où $\Lambda(s)$ est de croissance polynomiale?\\ On travaille en particulier dans le cadre des sources dynamiques: $\Lambda(s)$ est alors reli\'ee \`a l'op\'erateur de transfert du syst\`eme dynamique, et fait intervenir en particulier ses propri\'et\'es spectrales. On peut alors donner des conditions suffisantes (de nature g\'eom\'etrique ou arithm\'etique) sur le syst\`eme dynamique qui permettent de conclure.
Tafat Bouzid Hanane (LIPN, Université Paris 13) Titre : Asymptotique et loi limites des grammaires et automates.
Résumé : Dans le cadre des automates et grammaires fortement connexes, differents travaux permettent d’obtenir asymptotique et loi limite. La situation se complique singulièrement dans le cas non fortement connexe, nous donnons alors une classification de phénomènes universaux qui subsistent en matière d’asymptotique/loi limite. Ce qui a des applications à la génération aléatoire via la méthode de Boltzmann.
Vandomme Elise (Institut de Mathématiques, Université de Liège)
Titre : Complexité syntaxique d’ensembles d’entiers ultimement périodiques.
Résumé : Nous calculons la cardinalité du monoïde syntaxique du langage 0*rep_b (mN) composé des représentations en base b des multiples d’un entier m. Nous donnons aussi des bornes inférieures sur la complexité syntaxique de tout ensemble (ultimement) périodique d’entiers écrits en base b. Nous appliquons nos résultats à un problème très étudié : décider si un ensemble d’entiers reconnaissable en base b est ultimement périodique ou non. (Travail réalisé avec M. Rigo)
Vanier Pascal (LIF, Université de Provence)
Titre : Pavages et calculabilité.
Résumé : Les pavages et la récursivité sont intimement liés: en 1964, Berger prouvait l'indécidabilité de la pavabilité du plan, par la suite, Hanf et Myers prouvèrent qu'il existe des jeux de tuiles n'admettant aucun pavage récursif. Puis Simpson prouva en 2008 que les degrés Medvedev des pavages sont les mêmes que ceux des $pi^0_1$ de {0,1}. On prouve ici que pour tout $pi^0_1$ de {0,1}^N, il existe un jeu de tuiles qui lui est récursivement homéomorphe.
Wang BaoWei (LAMFA, UPJV)
Titre : Interactions of arithmetic and metic properties in beta expansion.
Résumé : In beta expansion, an accurate estimation on the length of a general cylinder constitues one main substance in studying their dimension theory. In this talk, some obervations on the relationship between the arithmetic and metic properties will be presented. As a consequence, we can study the dimension of the set of points with given rucurrent properties.