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 : Conception et élaboration d’une démarche de recherche et développement, d’études et prospective

- 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 au sein d’un secteur d’activité déterminé, aux échelles locale, nationale ou internationale

Bloc 4 : Veille scientifique et technologique à l’échelle internationale

- Acquérir, synthétiser et analyser les données et informations scientifiques et technologiques d’avant-garde à l’échelle internationale

- Disposer d’une compréhension, d’un recul et d’un regard critique sur l’ensemble des informations de pointe disponibles

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

- Disposer de la curiosité, de l’adaptabilité et de l’ouverture nécessaire pour se former et entretenir une culture générale de haut niveau

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