Objectifs :
This course concerns Master or PhD students having interest in theoretical aspects of computer science (formal methods, verification, automated reasoning, language theory, etc.).

Programme :
Formal language theory studies the finite representation of infinite sets of objects (e.g., words, trees, graphs). These representations can
be either descriptive, specifying logical properties of their members (e.g. planar or hamiltonian graphs), or constructive, describing how the members of the set are built.
In particular, constructive representations come with algebras that fix the class of objects and the operations considered. Then, recognizable sets are defined in terms of
congruence relations over the algebra, with a finite number of equivalence classes.

The goal of this course is to introduce the student to the connection between logical definability (using first-order and monadic second-order logics)
and recognisability (by automata, semigroups and algebras). This connection is the cornerstone of formal language theory, because it provides
robust characterisations of the classes of sets that can be represented finitely on a computer.

Pré-requis :
basic knowledge of set theory (sets, relations, functions, etc.) and boolean logic (the meaning of conjunction, disjunction, negation).

Equipe pédagogique :
Radu Iosif

Méthode pédagogique :
4 séances

Les Compétences et capacités visées à l'issue de la formation (fiches RNCP)

Arrêté du 22 février 2019 définissant les compétences des diplômés du doctorat et inscrivant le doctorat au répertoire national de la certification professionnelle. https://www.legifrance.gouv.fr/loda/id/JORFTEXT000038200990/

Bloc 1 : Concevoir et élaborer une démarche de recherche, de R&D ou d'innovation

- Disposer d'une expertise scientifique tant générale que spécifique d'un domaine de recherche et de travail déterminé

- Faire le point sur l'état et les limites des savoirs et des pratiques au sein d'un secteur d'activité déterminé, aux échelles locale, nationale ou internationale

Bloc 4 : Assurer une veille scientifique et technologique de haut niveau à l’échelle internationale

- Acquérir, synthétiser et analyser les données et les informations scientifiques et technologiques d’avant- garde à l’échelle internationale en développant un regard critique et distancié

- Dépasser les frontières des données et du savoir disponibles par croisement avec différents champs de la connaissance ou d'autres secteurs professionnels

La formation participe à l'objectif suivant :conforter la culture scientifique des doctorants dans leur champ disciplinaire ou en interdisciplinaire