| Résume | Un 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. |
