Compléments

Liste des compléments proposés

• Langages rationnels locaux
• Automates de Büchi et jeux
• Grammaires contextuelles et machines linéairement bornées
• Équivalence entre fonctions récursives et machines de Turing
• Espace logarithmique

Plan détaillé

Cours n° 1 : fonction récursives

(cf. [Aut92])

• Fonctions primitives récursives
  • définitions
  • exemples
  • fonction d'Ackermann
• Fonctions récursives
• Équivalence avec les machines de Turing

Cours n° 2 : automates de mot infinis et jeux

(cf. [PP04])

• Mots infinis
  • expressions rationnelles
  • automates de Büchi
  • automates de Muller
  • complémentation : preuve de Büchi
  • automates alternants
  • complémentation par les automates alternants à parité faible
• Jeux
  • jeux donnés par un ensemble de mots infinis
  • stratégies
  • jeux boréliens : théorème de Martin
  • arènes
  • jeux à parité
  • détermination des jeux à parité