Tree automata (M1 ENS Paris-Saclay)

Lecture 1: Introduction

Introduction

Exercises 1 : Recognizable Tree Languages and Finite Tree Automata

EX 1: First constructions

Lecture 2: Languages that aren’t regular tree ones

[L_1 ≝ \lbrace f(g(a, \square, b)^n \circ d, h(\square, c)^n \circ d) \mid n>0 \rbrace]

Exercises 2 : Non-Recognizable Languages and Commutative closure

EX 1 : an abstract language

Lecture 3: Monadic Second Order Logic

digraph { rankdir=TB; NFTA -> EMSO -> MSO; MSO -> WSkS, NFTA; WSkS -> NFTA; }

Exercises 3:

EX 1: Bottom-up transducers

Lecture 4: wSkS

wSkS

Exercises 3: wSkS

EX 1: The power of wSkS