Date: Fri, 25 May 2007 13:30:04 +0200 From: Christophe Tollu To: lipn.tous@lipn.univ-paris13.fr, tous@math.univ-paris13.fr, frederic.chyzak@inria.fr, goodenou@iutv.univ-paris13.fr, eric.laugerotte@univ-rouen.fr, penson@lptl.jussieu.fr, hayat.cheballah@gmail.com Subject: [CIP]: Journee rationnelle - programme Chers collègues, Le groupe de travail CIP organise le mardi 29 juillet une journée sur le thème "Orbites finies et rationalité". Le programme est le suivant : 10h30 : Houda ABBAD (EEDIS, Université de Sidi Bel Abbès) et Éric LAUGEROTTE (LITIS, Université de Rouen) "Manipulation d'expressions non commutatives" [résumé à la fin du message] 14h00 : Gérard H.E. Duchamp (LIPN, univ. Paris 13) "Sommabilité, finitude et rationalité en Informatique et en Physique" 15h30 : Frédéric Chyzak (INRIA Rocquencourt) "Sommation et intégration symboliques des fonctions spéciales et suites combinatoires" Les exposés auront lieu dans la salle B311 à l'Institut Galilée (bâtiment B, 3e étage, couloir du LIPN) [NB. Les exposés de l'après-midi auront peut-être lieu dans une autre salle, auquel cas un nouveau message sera envoyé) Vous êtes naturellement tous les bienvenus (pour tout ou partie de la journée). Nous accueillerons les participants à partir de 10h dans la salle A201 (salle café du LIPN, Institut Galilée, bâtiment A, 2e étage). Très cordialement, Christophe Tollu Résumé du 1er exposé : Les séries formelles ou les expressions non-commutatives sont des objets fréquemment rencontrés en combinatoire, et il est essentiel de pouvoir les manipuler afin de simplifier leurs écritures, si possible de façon automatique. Les expressions rationnelles permettent cela ce qui a été mis en évidence par Schützenberger en 1961 via les automates à multiplicités. Selon la nature des poids, de nombreuses fonctionnalités existent sur ces machines à états (opérations rationnelles, réduction, minimisation, élimination,...). Dans cet exposé, nous présenterons un algorithme décidant de l'équivalence de deux expressions rationnelles (si la nature des poids l'autorise). Ainsi : (a-b)*+(a+b)*=2(a+ba*b)* ? On détaillera plus précisément une généralisation de l'arbre syntaxique des expressions arithmétiques classiques due à l'apparition de l'opérateur étoile. Son utilisation apporte une efficacité notamment dans la constuction des automates à multiplicités qui est réalisée de façon quadratique en la taille de l'expression rationnelle. Mais aussi pour le calcul de poids de mots , la méthode ayant l'avantage d'être directe et de ne pas passer par les automates. Les structures et algorithmes nécessaires sont mis en oeuvre dans la bibliothèque MuPAD-Combinat du système de calcul MuPAD. Une présentation en sera faite à partir d'exemples classiques.