Words and trees are the most studied structures in Computer Science, as they can be given many interpretations in different very practical fields. For instance: a word can be seen as the sequence of outputs obtained from a computation, a tree can be seen as the different paths an algorithm can go, etc.
In this course, we study these objects from a theoretical point of view.
First, we give a panel of different machines, called automata, which allows us to consider words and trees (possibly infinite) in a computational way.
Second, we introduce different logical formalisms, allowing us to express different properties such as "my word contains the letter c somewhere after a letter b" or "my tree contains an infinite branch with only the letter a". We show that there is actually a very natural correspondence between these properties and automata.
Finally, we show another correspondence, between automata / logic and algebra: how can languages of words be studied though mathematical concepts.
The schedule of the course should roughly look as follow:
I] Automata over finite words
1) Recall of the definitions, determinisation, some decision problems...;
3) Monadic Second-Order Logic, and MSO <-> regular languages correspondence;
4) Characterisation of First-Order Logic in terms of automata;
II] Weighted automata
1) Definitions and some decision problems;
3) Fliess' theorem;
III] Automata for other structures
1) Buchi and M\"uller automata for infinite words;
2) Finite tree automata;
3) Infinite tree automata;
IV] Algebra and how it is linked to formal languages
1) Monoids;
2) Green's relations;
3) Finite monoid <-> regular languages correspondence;
4) (If time, then Schutzenberger's theorem (FO <-> aperiodic finite monoid). )
Although the course is theoretical, the involved tools are of limited technicality, and therefore are not an obstacle in understanding, nor enjoying the lecture and the proofs shown in it!
