Thèmes de recherche:

 

• Théorie des langages et Automates  

Le domaine de la théorie des langages est une thématique historique du LIFAR. Du point de vue de la recherche fondamentale, les problèmes étudiés portent sur le monoide libre, les monoides partiellement commutatifs (les monoides de trace de Cartier-Foata) et la théorie des codes. Cette recherche a des applications à l’optimisation des programmes en compilation et en model checking.

Cependant une importante part de l’effort de recherche est principalement axé sur les applications.

 Trois axes d’applications:

 

1. Validation d'applications temps réels:  Généralisation d’une classe de langages utilisée en validation hors-ligne d’applications temps-réel. Ceci peut être fait en utilisant un modèle basé sur des langages rationnels. Mais, à cause d’une propriété particulière de ces langages, on peut aussi utiliser un modèle basé sur la géométrie discrète et diminuer ainsi drastiquement le temps de calcul. Le but est le suivant : si on peut interpréter en termes de langages les propriétés qui font que le modèle géométrique est si efficace, on peut alors espérer obtenir de nouveaux algorithmes sur les automates avec de meilleures complexités. Outre les questions de théorie des langages et de géométrie discrète, cette problématique pose également des questions de combinatoire énumérative (énumération de polycubes par exemple).
2. Théorie des jeux et apprentissage. Les méthodes à noyaux sont largement utilisées dans les techniques d’apprentissage statistique comme les SVMs (Support Vector Machines). Cortes, Haffner et Mohri ont introduit une famille générale de noyaux basée sur les transducteurs pondérés, les noyaux rationnels, qui étendent les méthodes à noyaux à l’analyse des séquences de longueur variable avec ou sans poids. Cette nouvelle technique de classification prend en compte la contrainte sur la longueur variable des séquences qui apparaît dans de nouvelles applications en traitement du texte et en reconnaissance de la parole. L’explosion du volume de données à traiter (extraction, classification, ...) dans des domaines comme le traitement automatique des langages naturels, l’ingéniérie du web, ou encore l’ingéniérie des documents digitaux, a suscité de nombreux travaux sur l’inférence grammaticale des séries rationnelles de mots et d’arbres. Il paraît donc d’un grand intérêt d’étudier les noyaux rationnels des langages rationnels stochastiques et ceux des langages rationnels d’arbres (pondérés ou non), en vue de l’apprentissage des familles de langages correspondants.
3. Modélisation de structures arborescentes de document. Les automates d’arbres à multiplicités sont une généralisation à la fois des automates de mots à multiplicités et des automates d’arbres. Ils sont parfaitement adaptés pour la modélisation des structures de données arborescentes (pages web, documents digitaux) et sont de plus en plus utilisés comme modèles de langages en traitement automatique des langages naturels. Les défis posés par l’analyse de grandes masses de données, en extraction automatique en particulier, ont suscité de nouveaux travaux sur l’inférence grammaticale de ces automates.  

• Combinatoire des polynômes multivariés

  

  La généralisation de la théorie des polynômes orthogonaux au cas multivarié fait apparaître une difficulté majeure qui réside dans le choix des fonctions de base jouant le rôle des monômes. Il existe, en effet, une grande quantité de possibilités et une façon d'en choisir une consiste à supposer qu'un groupe fini agit sur les variables. C'est une des définitions possibles des polynômes de Jack: ce sont des polynômes orthogonaux multivariés à un paramètre dont la mesure associée provient d'un système de racines (dans le cas qui nous intéresse, il s'agit d'un système de type A_n; celui des groupes symétriques). En fait, plus que l'algèbre du groupe symétrique, c'est l'algèbre de Hecke double affine dégénérée (les deux sont confondues) qui intervient. Les polynômes de Jack sont alors obtenus grâce à un algorithme qui construit le graphe de Yang-Baxter et les produit de façon efficace; ce qui permet donc d'expérimenter. Ces polynômes ont été généralisés par Griffeth, il y a quelques années, au cas où les multiplicités sont prises dans une représentation irréductible du groupe symétrique. Dans une suite de deux articles en collaboration avec Charles F. Dunkl, professeur émérite de l'université de Virginie, nous avons montré que ces polynômes peuvent être obtenus, eux aussi, grâce à un procédé de type Yang-Baxter dont nous avons étudié la déformation à deux paramètres (polynômes de Macdonald) faisant intervenir l'algèbre de Hecke affine double non dégénérée. Ce qui a motivé ces travaux est un problème de physique lié à la description de l'effet de Hall fractionnaire quantique: trouver de bon polynômes candidats pour être des fonctions d'onde invariantes par translation globale des variables et ayant de bonnes propriétés de factorisation (sous certaines contraintes sur les variables). Les travaux de plusieurs physiciens, en particulier de Bernevig et Haldane, ont mis en évidence qu'une version symétrique des polynômes de Jack présente un intérêt particulier pour cette étude. Dans ce contexte, avec Thierry Jolicoeur du Laboratoire Physique Statistique et Modeles Statistiques de l'université Paris sud, nous avons étudié les polynômes de Jack de plus haut poids (c'est à dire invariant par translation) et nous avons exhibé des familles de tels polynômes. Nous avons donné aussi une version Macdonald des résultats (c'est à dire (q,t)-déformée). L'intérêt de la (q,t)-déformation réside dans le fait que les factorisations sont plus faciles à étudier car tous les facteurs sont différents.

  
  
  

  • Théorie classique des invariants et Information Quantique:

  

•     L'orbite des  3 qutrits et l'espace des formes normales     
  

  Un des problèmes majeurs de la théorie de l'information quantique consiste en la quantification de l'intrication. D'un point de vue mathématique, cette théorie manipule des espaces de Hilbert de dimension finie, représentant l'espace des systèmes de k particules, de la forme H = V₁ x V₂ x ... x V_ki est l'espace des états de la ième particule du système. La plupart du temps, ce sont des bits quantiques (qubits) qui sont considérés ce qui donne dim V_i = 2. La difficulté de cette théorie réside dans l'étude du comportement non classique, appelé intrication, qui apparaît dès lors que l'on a des systèmes d'au moins deux particules. Les systèmes intriqués sont ceux qui ne peuvent pas s'écrire sous la forme v₁ x v₂. Les propriétés de ces états ont été étudiés dans les années 1930 dans un célèbre article d'Einstein, Podolsky et Rosen, et sont connus sous le nom de paradoxe EPR. Depuis sa découverte le paradoxe EPR a été intensivement étudié par les physiciens et plus récemment par les mathématiciens. Il n'y a pas de consensus général sur la définition de l'intrication pour les systèmes ayant au moins trois parties. Klyachko a proposé de considérer comme intriqués les états qui sont semi-stables pour l'action du groupe SLOCC (Stochastic Local Operation assisted with Classical Communication) dans le sens de la théorie géométrique des invariants. C'est à dire les états dont au moins un invariant non trivial du groupe SLOCC ne s'annule pas. L'intérêt de la théorie géométrique des invariants réside dans le fait qu'elle contient des méthodes permettant de caractériser ces états sans calculer explicitement les invariants. Néanmoins pour les systèmes ayant trois parties et plus, peu de choses sont connues et seules quelques mesures d'intrications pertinentes ont été étudiées pour les systèmes de 3 ou 4 qubits. Dans le but de comprendre la signification de cette propriété, nous avons calculé explicitement les invariants dans quelques cas simples. Les propriétés de non localité d'un état intriqué sont invariantes sous l'action d'opérations unitaires agissant indépendamment sur chacun de ces sous-systèmes. L'idée de décrire l'intrication en utilisant la notion d'invariants locaux unitaires a été aussi explorée par les physiciens. Mais, à part dans les cas les plus simples, il y a en général beaucoup trop d'orbites et une classification complète ne peut pas être obtenue. Nous avons étudié une possibilité intermédiaire qui consiste à rechercher les covariants (dans les sens de la théorie classique des invariants) et à décrire une méthode pour en déduire les inva

  où V

  .

  riants locaux unitaires. Enfin, plus récemment, nous avons utilisé une autre approche : une description de l'intrication grâce à la géométrie algébrique et les variétés auxiliaires. Nous avons obtenu dans quelques cas simples, une classification géométrique que nous avons comparé avec les résultats obtenus grâce aux calculs des covariants. Cette approche a deux intérêts : d'une part elle est complémentaire du calcul des covariants et permet donc d'obtenir plus rapidement des résultats, d'autre part elle fournit des algorithmes permettant de déterminer dans quelle orbite se trouve un système donné.

 

• Cryptographie et calcul formel:
  

 En cryptographie, les résultats portent sur la complexité des attaques algébriques et en particulier l’algorithme F5 de J.-C. Faugère qui permet de résoudre efficacement les systèmes polynômiaux. D’autre travaux portent également sur les courbes elliptiques.

Approche

• Étude structurelle et combinatoire des modèles algébriques (mots, monoïde libre, polynômes) ; classification
• Étude algorithmique effective (automates finis, systèmes de calcul symbolique)
• Extension des modèles existants et construction de nouveaux modèles (automates d’arbres, algèbre de Hopf combinatoire, information quantique)

 

Séminaire

L'équipe "Combinatoire et algorithmes" a un séminaire hebdomadaire

animé par Carla Selmi.

 

Projets

• projet ANR-CARMA (2013-2016) : Combinatoire Algébrique, Résurgence, Moules et Applications . Programme "Blanc" de l’Agence Nationale de la Recherche, Projet ANR-12-BS01-0017

• Projet P.N.R. (C.E.R.I.S.T.) Algorithmique des automates d'arbre, noyaux rationnels et noyaux de graphes en vue d'apprentisage. Université Amar Télidji-Laghouat. Algérie
• Projet CMEP (Interaction entre l’informatique et la Combinatoire), Rouen-Alger

• Projet ANR-PhysComb: Physique combinatoire. Paris 13, Marne-La-Vallée, Lyon, Paris 6. Page résumant les activités du centre LabInfo IGM:  lien

• projet ANR- HopfCombOp (2006-2009): Algèbres de Hopf combinatoires, Opérades et props. Programme "Blanc" de l’Agence Nationale de la Recherche, Projet ANR-06-BLAN-0380.  lien

• Projet PEPS CerBISS (Certification de Bibliothèque de calculs en combinatoire algébrique), Villetaneuse.

 

Master ITA:

Les thématiques de l'équipe se retrouve dans les disciplines enseignées dans le master ITA

 

GDR IM:

Les membres de l'équipe font partie du GDR Informatique Mathématique.

 

En particulier des groupes de travail:

• SDA2: Systèmes dynamiques, Automates et ­Algorithmique (Valérie Berthé, Guillaume Theyssier)
• Combinatoire algébrique (Jean-Christophe Novelli)­
• Codage et cryptographie (La­urent Imbert)

 

Liens divers:

 

• CIAA: International Conference on Implementation and Application of Automata
• WORDS: International conference on words
  
• Sage Combinat:

Extension du système de calcul Sage pour la combinatoire algébrique. Projet soutenu par ANR et NSF (USA). Environ 20 développeurs, 40k lignes de Codes, 4000 fonctions (objectif 100k, 10000).

• PSTricks / pst-cox:

  Les polytopes de Coxeter

  PST-Cox est une bibliothèque de macros LaTeX permettant de dessiner des projections 2D de polytopes complexes réguliers. Les polytopes complexes réguliers sont des arrangements d'hyperplans ayant certaines contraintes dont les groupes des automorphismes sont engendrés par des pseudo réflexions (réflexions complexes).Ces objets généralisent les solides platoniques classiques.

  Dans l'exemple suivant sont représentés les polygones complexes β₃² et β₆² dont les arêtes sont respectivement triangulaires et hexagonales.

  

 

Evénements:

L'équipe C&A est impliquée dans l'organisation des événements suivants:

 

• WORDS'13  : WORDS 2013 will take place at Turku in Sept ember 2013
  
  

• CIAA'13: CIAA 2013, July 16-19, 2013

  18th International Conference on Implementation and Application of Automata
  
  - Saint Mary's University, Halifax, Nova Scotia, Canada.

 

Autres conférences:

• FPSAC'2013: 25ème conférence internationale sur les séries formelles et la combinatoire algébrique.  Paris, du 24 au 28 Juin 2013

 

 

.

• SLC73:

 

THE 73rd SÉMINAIRE

LOTHARINGIEN DE COMBINATOIRE

(Wien, Erlangen, Marne-la-Vallée)

will take place at the

Bundesinstitut für Erwachsenenbildung Strobl (Wolfgangsee) Bürglstein 1-7 A-5350 Strobl (Austria) Tel.: +43(0)6137-6621-0, Fax.: +43(0)6137-6621-116

from Sunday, September 7, 2014 (evening) to Wednesday September 10, 2014 (afternoon).

 

Evénements, années précédentes:

 

• CIAA'12:
• Journée SDA2:

  Journées Machines à états finis et Combinatoire en l'honneur de

  Jean-Marc Champarnaud

  Le LITIS (Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes) organisera du 11 au 13 juin 2012 à Rouen une rencontre SDA2 (Systèmes Dynamiques, Automates et Algorithmique) du pôle Algorithmique et Combinatoire du GDR IM (Informatique Mathématique) du CNRS.
  Cette rencontre constituera la réunion annuelle du groupe de travail SDA2. Elle sera l'occasion pour les jeunes chercheurs de présenter leurs travaux dans ces domaines. Des tutoriels seront également dispensés par des chercheurs confirmés.

  
  

 

 

 

 

 

 

• CIAA'11:

 

 

• WORDS'11:

• Journée CombAlg: