28 mai 2019, Caen
Une journée de l’axe AlgoComb aura lieu à Caen, en salle S-351, bâtiment Sciences 3, Campus II, le 28 mai 2019.
Programme (les résumés des exposés se trouvent plus bas):
- 10h-10h25 : Accueil
- 10h25 -10h30 : Présentation de NormaStic et du cadre de la rencontre
- 10h30-11h30 : 2 exposés (session 1)
- Amazigh Amrane (Rouen, automates & logiques)
Logique et automates de posets série-parallèles indexés par des ordres linéaires dénombrables et dispersés. - Clément Miklarz (Rouen, automates)
Les langages k-blocs déterministes
- Amazigh Amrane (Rouen, automates & logiques)
- 11h30-12h : Pause
- 12h-13h : 2 Exposés (session 2)
- Theo Grente (Caen, modèles de calcul)
Caractérisation logique du temps minimal des automates cellulaires - Pablo Rotondo (Marne-la-Vallée, aléa & combinatoire des mots)
Récurrence des mots Sturmiens: le cas des mots Sturmiens substitutifs.
- Theo Grente (Caen, modèles de calcul)
- 13h-14h30 : Déjeuner
- 14h30-15h30 : 2 exposés (session 3)
- Younès Hatri (Rouen, cryptologie & théorie des nombres)
La cryptographie basée sur l’identité - Valentin Suder (Rouen, cryptologie & codes)
Les fonctions APN, une histoire de Codes
- Younès Hatri (Rouen, cryptologie & théorie des nombres)
- 15h30-16h : Pause
- 16h-17h30 : 3 Exposés (session 4)
- Matthieu Dien (Caen, aléa & combinatoire analytique)
Compter et générer aléatoirement les extensions linéaires - Julien Courtiel (Caen, aléa & cartes)
Diagrammes de cordes et cartes enracinées (mais à quoi sert une bijection ?) - Paul Dorbec (Caen, graphes)
Reconfiguration combinatoire: l’exemple des ensembles dominants.
- Matthieu Dien (Caen, aléa & combinatoire analytique)
Pour venir en partant de la gare SNCF:
- Prendre le bus A à la station « Gare SNCF Rue d’Auge » en direction de « Campus 2 » (à 2 minutes de la gare)
- Descendre à « Campus 2 » (terminus)
Durée: environ 30 minutes
Résumés des exposés:
- Amazigh Amrane (Rouen, automates & logiques)
Logique et automates de posets série-parallèles indexés par des ordres linéaires dénombrables et dispersés.
Plusieurs connexions ont été trouvées entre les différents types d’automates et les logiques dans la littérature. D’abord, Buchi a montré que les automates de Kleene et la logique MSO interprétée sur les mots finis ont la même expressivité. Ceci implique la décidabilité de la logique MSO quand elle est interprétée sur les mots finis. Cette même logique a été prouvée décidable lorsqu’elle est interprétée sur des mots de longueurs dénombrables (Rabin). Les automates de Kleene peuvent servir comme modèles pour les programmes séquentiels. En effet, on peut voir chaque lettre de l’alphabet de l’automate comme une instruction et donc assimiler mot et exécution de programme séquentiel. Cette assimilation ainsi que le théorème de Buchi sont utilisés notamment pour la vérification de programmes. Il existe plusieurs types d’automates modélisant les programmes concurrents. Parmi eux, on s’intéresse aux automates branchants proposés par K. Lodaya et P. Weil. C’est une généralisation des automates de Kleene avec deux nouveaux types de transitions : Fork et Join, permettant de modéliser le parallélisme. Les automates branchants ne reconnaissent plus que des mots, mais plutôt des ensembles partiellement ordonnés (posets) de lettres qui sont équivalents aux posets finis sans N. Dans ce travail, on s’intéresse aux automates branchants introduits par N. Bedon et C. Rispal qui sont une généralisation des automates branchants de Lodaya et Weil et des automates d’ordres linéaires de Bruyère et Carton. Ces automates reconnaissent les langages de posets sans N dont les chaînes sont des ordres linéaires dénombrables et dispersés et les antichaines sont finies. On montre l’équivalence d’expressivité entre ces automates et une extension de MSO par la logique de Presburger nommée P-MSO. Les construction d’un formalisme à l’autre étant effective, on en déduit la décidabilité de P-MSO.
- Clément Miklarz (Rouen, automates)
Les langages k-blocs déterministes.
Une expression rationnelle est 1-non-ambiguë si son automate des positions est déterministe, et un langage est 1-non-ambigu s’il peut être représenté par une expression 1-non-ambiguë. Brüggemann-Klein et Wood caractérisent cette propriété sur un langage en partant de son AFD minimal et en appliquant une procédure: le BW-test. La famille des langages bloc-déterministes, étudiée par Giammarresi et al. puis par Han et Wood, est une extension de celle des langages 1-non-ambigus, où l’on utilise des mots à la place des lettres dans les expressions. Nous avons montré que certains résultats précédemment obtenus étaient erronés, et que d’autres avaient été incorrectement démontrés. Nous présenterons les premiers éléments de caractérisation de cette famille, sa hiérarchie propre par rapport à la taille maximum des blocs, et sa stricte inclusion dans les langages rationnels.
- Theo Grente (Caen, modèles de calcul)
Caractérisation logique du temps minimal des automates cellulaires
Les automates cellulaires représentent le modèle par excellence du calcul parallèle et local. De la même façon qu’on sait caractériser en logique les langages rationnels, on cherche à caractériser/programmer en logique les calculs des automates cellulaires. Le comportement local et déterministe des automates cellulaires s’exprime naturellement par des clauses de Horn portant sur une arithmétique locale du prédécesseur. L’outil principal utilisé est une méthode de normalisation transformant une formule en une formule équivalente qui imite un circuit grille. Dans cet exposé, je présenterai l’exemple du temps réel (= temps minimal) des automates cellulaires, intéressant par sa puissance de reconnaissance (multiplication d’entiers, majorité…) et son polymorphisme.
- Pablo Rotondo (Aléa & combinatoire des mots)
Récurrence des mots Sturmiens: le cas des mots Sturmiens substitutifs.
En combinatoire des mots, la fonction de récurrence peut être vue comme le temps d’attente nécessaire pour découvrir tous les facteurs du mot de taille donnée $n$. Elle est donc liée à la complexité du mot, égale au cardinal des facteurs de longueur $n$. Les mots Sturmiens sont fondamentaux en combinatoire des mots, car ce sont les mots non périodiques de plus basse complexité. Les mots Sturmiens substitutifs, construits par substitution de lettre, forment une sous classe particulièrement intéressante des mots Sturmiens. Il est donc naturel d’étudier, de manière probabiliste, la fonction de récurrence sur ces deux classes de mots. Nous exhibons des fortes similarités entre la distribution limite de la récurrence sur chacune des sous classes. (Travail commun avec Brigitte Vallée)
- Younès Hatri (Rouen, cryptologie & théorie des nombres)
La cryptographie basée sur l’identité
La cryptographie basée sur l’identité parvient à résoudre les problèmes liés à l’authentification, à la gestion et à la révocation des clés publiques. Le concept de la cryptographie basée sur l’identité a été introduit par Shamir en 1984 avec l’idée de créer un schéma de chiffrement pour lequel la clef publique est l’identité de l’utilisateur, par exemple ses nom, prénom, email, etc. Le protocole proposé par Shamir utilise le schéma RSA mais sans fournir une preuve de sécurité. La recherche d’un schéma de chiffrement basé sur l’identité est restée alors ouverte jusqu’à 2001 où Cocks puis Boneh et Franklin ont proposé indépendamment des cryptosystèmes qui répondent relativement aux conditions de sécurité et d’efficacité. Utilisant le notion de tore algébrique, nous donnons une généralisation au schéma de Boneh et Gentry. L’idée est d’utiliser à la place du symbole de Jacobi modulo un entier composite N, un symbole de résidu de puissance. Cela améliore l’efficacité en permettant à l’expéditeur d’envoyer plus de bit de données.
- Valentin Suder (Rouen, cryptologie & codes)
Les fonctions APN, une histoire de Codes
Les attaques génériques contre les algorithmes de cryptographie symétrique se sont étendues, généralisées et surtout complexifiées au cours des années et à l’aide d’une communauté de cryptographes active et ingénieuse. Cependant, il apparaît que parmi toutes ces attaques, la majorité sont en fait des variantes des attaques classiques dont l’une des plus célèbre est l’attaque différentielle, celle qui va nous intéresser le plus lors de cet exposé. De fait, le critère de sécurité contre les attaques différentielles, appelée uniformité différentielle, reste le critère de sécurité principal contre ces variantes aussi. Les fonctions qui sont optimales pour ce critère différentiel sont communément appelées fonctions APN (pour Almost Perfect Nonlinear) et leur rareté ainsi que leur utilité, en cryptographie bien sûr mais pas seulement, en font des objets d’étude de permier choix. Définies formellement dans les années 90, les fonctions APN forment aujourd’hui le noyau d’un domaine de recherche à part entière des mathématiques discrètes. Leur unicité font qu’elles ont en effet des applications dans des domaines variés (e.g. théorie des séquences, géométrie projective, etc…) et bénéficient donc de méthodes et d’outils différents pour les décrire et les étudier. L’aspect sur lequel nous nous pencherons et celui qui nous provient de la théorie des codes correcteurs d’erreurs. Historiquement, les codes correcteurs d’erreurs étaient en effet le premier angle d’étude pour les fonctions APN, puisque les premiers exemples de ces fonctions, qui étaient monômiales, provenaient directement des codes cycliques. Cette présentation sera donc l’occasion de revisiter, à travers des résultats classiques et plus avancés, l’histoire des fonctions APN et du rôle majeur que les codes correcteurs y jouent. Nous aborderons ainsi l’aspect code cyclique des fonctions puissances et l’importance de ces sous-classes. Afin de permettre une hypothétique classification, nous verrons une équivalence de fonctions dite CCZ, qui conserve entre autre l’uniformité différentielle, et parlerons surtout de son origine en tant qu’équivalence de codes. Nous verrons aussi comment cette équivalence, et la représentation en terme de codes qui lui est associée, est au centre de la découverte de la seule fonction APN bijective en dimension paire connue à ce jour. Finalement, nous nous intéresserons à la représentation des fonctions quadratiques APN en tant que codes de poids constant en métrique rang.
- Matthieu Dien (Caen, aléa & combinatoire analytique)
Compter et générer aléatoirement les extensions linéaires
Une extension linéaire associée à un ordre partiel est un ordre total qui respecte les contraintes de l’ordre partiel. Nous souhaiterions connaître le nombre d’extensions linéaires associée à un ordre partiel donné. Pour ce faire, nous rappelons la notion de polytope d’ordre (introduite par Stanley) dont le volume est lié au nombre d’extensions linéaires. Notre contribution donne un principe de décomposition d’un ordre partiel, qui permet de construire une formule symbolique dont l’évaluation donne le volume du polytope d’ordre. Nous utilisons aussi cette formule pour générer aléatoirement des extensions linéaire, de manière uniforme.
- Julien Courtiel (Caen, aléa & cartes)
Diagrammes de cordes et cartes enracinées (mais à quoi sert une bijection ?)
Cet exposé présentera une bijection entre deux familles d’objets combinatoires : les diagrammes de cordes connexes d’un côté, et les cartes combinatoires sans ponts de l’autre. Bien que ces deux familles combinatoires ont été considérablement étudiées, il semblerait que ce lien bijectif soit nouveau. J’expliquerai donc cette bijection, narrerai l’histoire de sa découverte et exposerai les conséquences intéressantes d’une telle bijection. Ces travaux sont co-réalisés avec Karen Yeats (Université de Waterloo, Canada) et Noam Zeilberger (Université de Birmingham).
- Paul Dorbec (Caen, graphes)
Reconfiguration combinatoire: l’exemple des ensembles dominants.
Étant donnés deux objets combinatoires satisfaisant une propriété donnée, la question de la reconfiguration consiste à tenter de passer d’un objet à l’autre pas à pas en maintenant la propriété donnée. On s’intéressera ici à la question appliquée à des ensembles de sommets dans un graphe, et en particulier les ensembles dominants. On dit d’un sommet qu’il domine son voisinage (lui-même inclu); un ensemble dominant est un ensemble de sommets qui domine l’ensemble du graphe. Pour reconfigurer des ensembles dominants, on s’intéressera principalement à l’opération de glissement de jeton, qui consiste à déplacer un jeton d’un sommet à un voisin le long d’une arête. Nous présenterons quelques résultats de complétude et algorithmes pour ce problème, selon les classes de graphes étudiées. Principalement, nous montrerons que le problème admet un algorithme polynomial pour certaines classes où le problème d’ensemble dominant est polynomial, mais PSPACE dur pour d’autres, incluant des graphes de largeur arborescente bornée.