Séminaire du 9 juillet 07, Bruno Salvy, Projet Algorithmes.
Équations différentielles pour les séries algébriques
Le calcul des coefficients des séries algébriques (c'est-à-dire solutions de polynômes en deux variables) est important pour l'énumération des langages context-free et pour leur génération aléatoire. Une méthode classique repose sur l'utilisation d'équations différentielles linéaires. Nous présentons cette méthode et ses avantages du point de vue de la complexité. Nous montrons ensuite qu'il est possible d'améliorer l'efficacité de cette méthode en recherchant une équation différentielle d'ordre élevé, mais avec des coefficients de degré modéré. Nous en déduisons un algorithme plus efficace que ses prédécesseurs, s'étant affranchi du poids de trop nombreuses singularités apparentes.
Il s'agit d'un travail en commun avec Alin Bostan, Frédéric Chyzak, Grégoire Lecerf et Éric Schost.