• Logique, automate et langage formel

La complexité et la calculabilité permettent de classifier et comprendre la difficulté intrinsèque des problèmes. Nous pouvons ainsi montrer rigoureusement qu'un algorithme est optimal en temps ou en espace de calcul pour résoudre un problème donné. Pour cela, nous développons des outils fondamentaux impliquant la logique, les graphes, les bases de données.