• Lundi 11 juin
  • 11h00-13h30 : Accueil et repas
  • 13h30-14h30 : Marc Tommasi - Tutoriel 1 (1/2)
    Quelques éléments à propos de l'inférence grammaticale
  • 14h30-15h00 : Pascal Caron
    Langages rationnels 1-non ambigus et extensions
  • 15h00-15h30 : Kevin Perrot
    Selon Kadanoff, le sable est-il liquide ?
  • 15h30-16h00 : Pause
  • 16h00-17h00 : Bruce Watson
    New partial-derivatives-based NFA construction algorithm
  • 17h00-17h30 : Nadia Ouali Sebti
    Conversion d’une expression rationnelle d’arbre en un automate
  • 17h30-18h00 : Vincent Carnino
    Factorisations et automate universel des ω-langages
  • 18h30-20h30 : visite organisée
• Mardi 12 juin
  • 9h30-10h30  : Marc Tommasi - Tutoriel 1 (2/2)
    Quelques éléments à propos de l'inférence grammaticale
  • 10h30-11h00 : Pause
  • 11h00-12h00 : Jean-Éric Pin
    Le produit de concaténation et ses variantes
  • 12h00-12h30 : Fabien Durand
    Decidability for morphic sequences
  • 12h30-14h30 : Repas
  • 14h30-15h30 : Michel Rigo - Tutoriel 2 (1/2)
    Autour des systèmes de numération abstraits
  • 15h30-16h00 : Vincent Nesme
    Automates cellulaires linéaires réversibles et simulation
  • 16h00-16h30 : Pause
  • 16h30-17h30 : Julien David
    Énumération asymptotique des automates minimaux
  • 18h30-23h00 : dîner de gala
• Mercredi 13 juin
  • 9h30-10h30 : Michel Rigo - Tutoriel 2 (2/2)
    Autour des systèmes de numération abstraits
  • 10h30-11h00 : Pause
  • 11h00-12h00 : Émilie Charlier
    Complexité syntaxique et numérations
  • 12h00-12h30 : Julien Provillard
    Mode d'acceptation pour ω-langages
  • 12h30-14h30 : repas
  • 14h30-15h30 : Nathalie Aubrun
    Dynamique symbolique sur des groupes
  • 15h30-16h00 : Pause
  • 16h00-16h30 : Yvan Le Borgne
    Construction de systèmes dynamiques probabilistes pour des énumérations d'animaux dirigés
  • 16h30-17h00 : Benjamin Hellouin
    Comportement asymptotique d'une famille d'automates cellulaires simples : résultats quantitatifs
  • 17h00-17h30 : Mohamed Dahmoune
    Clone with Differentia over infinite alphabet is automatic

---

Tutoriels

Autour des systèmes de numération abstraits

Michel Rigo (Institut de Mathématiques, Université de Liège, Belgique)

Un système de numération, comme notre système décimal usuel, peut être vu comme une bijection entre l'ensemble des entiers naturels et le langage formé des représentations de ces entiers. Lorsque l'on considère, de façon générale, une numération basée sur une suite strictement croissante d'entiers et pour laquelle les représentations sont obtenues par un algorithme glouton, la bijection qui à un entier associe sa représentation préserve l'ordre naturel. Ainsi, un système de numération abstrait est la donnée d'un langage L infini (le plus souvent régulier) ordonné par ordre généalogique croissant. L'entier n est alors représenté par le n-ième mot du langage L.
L'introduction, il y a une dizaine d'années, de ces systèmes abstraits a été motivée par le théorème de Cobham de 1969 qui s'intéresse aux ensembles reconnaissables d'entiers. Un ensemble X d'entiers est dit S-reconnaissable, pour une numération fixée S, si l'ensemble des représentations dans le système S des éléments de X forme un langage régulier. Ainsi les ensembles S-reconnaissables sont, d'un certain point de vue, particulièrement simples puisque décrits par un automate fini. Le théorème de Cobham stipule que les seuls ensembles d'entiers simultanément reconnaissables pour deux bases entières k et l suffisamment indépendantes, à savoir multiplicativement indépendantes, sont exactement les unions finies de progressions arithmétiques. Ce théorème a été le point de départ de nombreux travaux de recherche au cours de ces quarante dernières années (généralisations à des numérations non standards, à plusieurs dimensions, formalisme logique,... ).
Dans ce survol liant théorie élémentaire des nombres et théorie des automates, nous nous proposons de présenter quelques questions et développements en lien directe avec cette question générale : existe-t-il un lien entre les propriétés arithmétiques des nombres (e.g., carré parfait, nombre premier, critère de divisibilité, ...) et les propriétés syntaxiques de leurs représentations ? Les propriétés décrites par automates finis sont-elles, par exemple, stables en appliquant des opérations arithmétiques élémentaires comme l'addition ou la multiplication par une constante ? Les automates permettent également de tracer des liens avec la combinatoire des mots (suites automatiques au sens d'Allouche et Shallit et plus généralement mots morphiques engendrés par substitution) ou d'exprimer certains problèmes de décision dont la solution revient à étudier la complexité en nombre d'états (state complexity) de certaines familles de langages.

Quelques éléments à propos de l'inférence grammaticale

Marc Tommasi (LIFL, Université de Lille 3, France)

Dans cet exposé, j'introduis la problématique de l'inférence d'une représentation d'un langage à partir d'exemples. Les langages considérés sont des langages réguliers de mots ou d'arbres ou plus généralement des séries rationnelles. Les représentations sont des machines à états finis déterministes ou non. Deux approches principales sont présentées, l'une que je qualifie d'incrémentale et une seconde qui est globale.
Les motivations initiales de ce travail étaient tournées vers l'estimation de distributions de structures complexes. Mais les solutions proposées nous permettent de mettre en évidence des liens importants entre plusieurs thématiques : entre apprentissage automatique, théorie des langages formels mais aussi algèbre linéaire et théorie des graphes.

 

---

Exposés invités

Dynamique symbolique sur des groupes

Nathalie Aubrun (Université de Turku, Finlande)

Dans cet exposé je présenterai quelques problèmes de dynamique symbolique sur des groupes. Les décalages de type fini sont des objets bien compris en dimension 1, mais deviennent autrement plus complexe en dimension supérieure. Je présenterai quelques résultats et problèmes qui mettent en évidence comment la structure du groupe influe sur les propriétés des décalages.

Complexité syntaxique et numérations

Émilie Charlier (Université libre de Bruxelles, Belgique),

La complexité en nombre d'états (state complexity) d'un langage régulier est le nombre d'états de son automate minimal. La complexité syntaxique est le cardinal du monoïde syntaxique associé. La première ne prend en compte que le contexte à droite alors la seconde considère les contextes à gauche et à droite.
Nous nous intéressons aux liens entre les nombres et leurs représentations. Dans le système décimal, un nombre est pair si sa représentation se termine par 0, 2, 4, 6 ou 8, ce qui donne lieu à ensemble de représentations simple, c'est-à-dire reconnu par automate. Plus généralement, dans une base entière, tout critère de divisibilité se traduit par un automate.
Etant donné un ensemble d'entiers, nous voulons répondre aux questions suivantes. Quel est le nombre d'états de l'automate minimal associé. Quelle est la complexité syntaxique associée ? Ces questions s'étendent à des numérations plus générales.
Ces problèmes sont motivés par des problèmes de décidabilité. Par exemple : étant donné un automate reconnaissant un ensemble d'entiers, décider si cet ensemble est ou non ultimement périodique.

Énumération asymptotique des automates minimaux

Julien David (LIPN, Université de Paris 13, France),

Un automate minimal est le plus petit automate déterministe accessible complet reconnaissant un langage rationnel donné.
Cet automate étant canonique, l'énumération des automates minimaux équivaut à l'énumération des langages rationnels.
On donnera une estimation asymptotique du nombre d'automates minimaux en étudiant leur proportion parmi les automates déterministes accessibles complets, dont la combinatoire est mieux connue.
La preuve de ce résultat utilise des méthodes de combinatoire bijective ainsi que des méthodes probabilistes.

Le produit de concaténation et ses variantes

Jean-Éric Pin (LIAFA, CNRS, Université de Paris 7, France),

Le produit de concaténation est une opération très importante pour l'étude des langages rationnels. Il en existe plusieurs variantes : produit marqué, non-ambigu, déterministe, à compteur...
Nous présenterons divers résultats, anciens ou récents, ainsi que quelques questions ouvertes relatives à ces opérations.

New partial-derivatives-based NFA construction algorithm

Bruce Watson (FASTAR Research Group, Centre for Knowledge Dynamics and Decision-Making, Stellenbosch University, South Africa)

In this talk, I will present a new algorithm constructing a nondeterministic finite automaton (NFA) from a regular expression. The algorithm displays a number of interesting properties :

• More or less direct construction of the NFA without large intermediate data-structures.
• The resulting NFA is usually very small.
• It is easier to explain, and prove correct, than many similar algorithms.
• The NFA states are annotated with additional information, making it easier to debug regular expressions.
• It lends itself to efficient implementation, using very little memory during construction.

We will begin with an overview of derivatives and related optimizations.

 

---

Exposés réguliers

Factorisations et automate universel des ω-langages

Vincent Carnino (LIGM - Laboratoire d'informatique Gaspard-Monge UMR 8049 - Marne la Vallée )

On étend dans ce travail la notion de factorisations définie sur les mots par Conway aux mots infinis. On montre que plusieurs types de factorisations
sont nécessaires pour caractériser un langage. De même que pour les mots finis, on montre que tout langage ω-rationnel admet un nombre fini de factorisations.
Ces factorisations sont calculables à l'aide de l'ω-semi-groupe syntaxique du langage [4]. De manière plus surprenante, la déterminisation (subset construction) d'un automate prophétique (automate de Büchi ”co-déterministe” [1]) permet aussi de calculer certaines de ces factorisations.
On montre ensuite comment ces factorisations permettent de définir un automate de Büchi canonique pour chaque langage ω-rationnel, en étendant la définition d'automate universel [3, 5] des langages de mots finis. C'est à notre connaissance la seule définition d'un automate de Büchi canonique pour les langages ω-rationnels.
Enfin, quelques propriétés de cet automates sont étudiés. On montre que tout automate de Büchi, mis sous une forme normale simple, qui reconnaît un certain langage admet une image morphique dans l'automate canonique du langage, qui est donc un automate universel.
Par ailleurs, on prouve qu'il s'agit du plus petit automate ayant cette propriété...

Langages rationnels 1-non ambigus et extensions

Pascal Caron (LITIS, Université de Rouen)

Afin de savoir si un fichier XML correspond au modèle que l'on s'est fixé, on utilise un fichier de modèles (DTD) qui comporte une grammaire. Ces grammaires sont composées de règles. La partie droite de ces règles est une expression rationnelle avec une forme particulière. Bruggemann-Klein et Wood ont formalisé  ces expressions rationnelles et ont montré qu'elles ne dénotaient qu'une partie des langages rationnels. Ces expressions ont ceci de particulier que lors de la lecture d'un mot du langage, on peut faire correspondre de manière unique chaque lettre lue avec la lettre de l'expression rationnelle qui l'engendre. L'automate de position qui en résulte est déterministe. Les langages reconnus sont appelés langages 1-non-ambigus. Dans cet exposé, nous rappellerons les principaux résultats concernant ces langages. Nous étudierons plusieurs des extensions  envisagées et nous proposerons plusieurs problèmes ouverts.

Clone with Differentia over infinite alphabet is automatic

Mohamed Dahmoune (LACL, Université Paris-Est Créteil)

We establish the automaticity of several structures whose domain is a set of finite word written in a countable infinite alphabet. We are interested, in particular, to the prefix relation, the clone predicate (a word that ends with two identical letter), and  the differentia predicate (a word whose letters are all distinct). The study of the automaticity of these structures leads to claim the decidability of its first-order theory. The use of  M-automata introduced by Alexis Bès allows us to obtain more extensive results of decidability. Furthermore, some results of decidability of monadic second-order theory are shown in this presentation.

Decidability for morphic sequences

Fabien Durand (LAMFA, Université de Picardie)

In this talk we will give a proof of the decidability of the following problems : the ultimate periodicity and the uniform recurrence of morphic sequences and other problems.
We will use the characterization of primitive substitutive sequences in terms of derived sequences.

Comportement asymptotique d'une famille d'automates cellulaires simples : résultats quantitatifs

Benjamin Hellouin (LATP, Université de Provence)

Un automate à glisseurs modélise deux types de particules de vitesses différente qui s'annihilent au contact. Partant d'une configuration aléatoire, on observe une diminution du nombre de particules avec le temps. Pour des résultats plus précis, nous nous intéressons tout d'abord au temps d'attente avant le prochain passage d'une particule, pour lequel des résultats dans un cas particulier existaient déjà. En traçant un parallèle entre le comportement de l'automate et celui d'une certaine marche aléatoire, nous étendons les résultats à une large classe de mesures initiales et à une famille d'automates ayant un comportement similaire, et les mêmes méthodes fournissent des résultats sur d'autres paramètres tels que la densité de particules ou la vitesse de convergence vers la mesure limite.

Construction de systèmes dynamiques probabilistes pour des énumérations d'animaux dirigés

Yvan Le Borgne (LaBRI, CNRS-Université de Bordeaux 1)

Depuis les années 80, diverses énumérations des animaux dirigés sur le réseau carré ont été mis en
relation avec la densité de certains modèles de gaz sur la ligne. Je propose de prolonger cette relation pour formaliser un lien entre ces questions et des systèmes dynamiques probabilistes sur le carré unité.
La preuve passe par l'analyse de l'exécution d'une sorte de machine de Turing probabiliste.
Pour les systèmes dynamiques associés aux problèmes combinatoires les plus simples, les connaissances issues des travaux sur le problème combinatoire permettent certaines observations. L'étude des systèmes dynamiques les plus intéressant combinatoirement reste à faire (ou sont peut-être déjà fait par des dynamiciens sans que je le sache).

Automates cellulaires linéaires réversibles et simulation

Vincent Nesme (CAPP - LIG, Université Joseph Fourier, Grenoble)

L'étude des relations de simulation entre automates cellulaires est encore, malgré de vigoureux déblayages, encore largement à l'état de friche. Il reste en général
très difficile de prouver qu'un AC n'en simule pas un autre, même lorsque cela paraît relativement évident.
*Selfsimilarity, Simulation and spacetime symmetries*, présenté à Automata 2011, proposait d'étudier la classe des AC linéaires, en introduisant une technique permettant justement de prouver dans certaines situations qu'un AC n'en simule pas un autre.
Je vais montrer comment adapter cette technique pour résoudre une question restée ouverte en conclusion de cet article : "Existe-t-il un automate cellulaire réversible qui soit capable de simuler l'identité mais pas son propre inverse ?".

Conversion d’une expression rationnelle d’arbre en un automate

Nadia OUALI SEBTI (LITIS, Université de Rouen)

Les automates d’arbres sont utilisés dans divers domaines tels que la vérification, l’apprentissage, la linguistique ou encore la validation de schémas de langages XML. Dans cet exposé, nous présentons une nouvelle construction qui transforme une expression rationnelle d’arbres E en un automate d’arbres avec une complexité en O(|E|3 ), généralisant ainsi la construction classique de l’automate de positions dans le cas des mots.
Travaux réalisés avec Eric Laugerotte et Djelloul Ziadi.

Selon Kadanoff, le sable est-il liquide ?

Kevin Perrot (ENS de Lyon)

Le modèle de pile de sable à la Kadanoff est un système dynamique discret en espace et en temps, non déterministe. Pour un entier D>1, partant d'un nombre fini N de grains empilés on applique une règle d'évolution qui fait chuter les grains dans une direction : si la différence de hauteur entre la colonne i et la colonne i+1 est au moins D, alors D-1 grains chutent de la colonne i, 1 grain tombe sur chacune des D-1 colonnes i+1,i+2,...,i+D-1. Pour D et N fixés, on arrivera toujours à la même configuration stable : le système converge vers un unique point fixe.
On s'intéresse à la question suivante : peut-on décrire simplement la forme du point fixe en fonction de D et de N ? Expérimentalement, on observe une série de vaguelettes apparaître de façon très régulière sur la queue de la pile de sable. Nous verrons une approche inductive dans laquelle on ajoute les grains un à un, nous permettant de prouver cette émergence pour D=3, et discuterons des difficultés rencontrées pour généraliser ce résultat.
Travaux réalisés avec Eric Rémila.

Mode d'acceptation pour ω-langages

Julien Provillard (I3S, Université de Nice Sophia Antipolis)

Les modes d'acceptation pour automates finis sur mots infinis sont des conditions qui permettent de sélectionner un sous-ensemble des chemins de l'automate. Les deux conditions les plus connues sont les conditions de Büchi et de Muller. D'autres conditions définies de la même façon ont déjà été étudiées dans la littérature. Nous nous intéressons ici à de nouveaux modes d'acceptation et comparons les classes qu'ils définissent aux classes existantes ainsi qu'aux ensembles de la hiérarchie borélienne. Cette classification prend également en compte l'éventuelle structure de l'automate (déterminisme, complétude).