• Logic, automaton and formal language

Complexity and calculability make it possible to classify and understand the intrinsic difficulty of problems. We can thus rigorously show that an algorithm is optimal in time or computational space to solve a given problem. For this, we develop fundamental tools involving logic, graphs, databases.