Séminaires : Séminaire Général de Logique

Equipe(s) : lm,
Responsables :O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson
Email des responsables :
Salle : salle 2015
Adresse :Sophie Germain
Description

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion


Orateur(s) Guillaume Malod - Equipe de Logique Mathématique, IMJ-PRG,
Titre Les séries d'arbres et la complexité algébrique
Date19/11/2018
Horaire15:10 à 16:10
RésumeUn résultat de Nisan de 1991 donne une caractérisation exacte de la complexité de calcul d'un polynôme non-commutatif par un modèle appelé branching program, via les rangs de certaines matrices. Fijalkow, Lagarde, Ohlmann et Serre ont récemment remarqué que ces résultats étaient en fait des cas particuliers de théorèmes sur les séries formelles de mots et d'arbres et ont cherché à les exploiter ceux-ci pour les appliquer à la complexité algébrique.
J'essaierai de faire une présentation synthétique de ces différents résultats.
Sallesalle 2015
AdresseSophie Germain
© IMJ-PRG