Content
The course provides a comprehensive introduction to tree automata.
A selection of the following topics will be discussed:
-
regular tree languages
-
tree automata
-
minimization
-
closure properties
-
decision problems
-
regular grammars
-
regular expressions
-
regular relations
-
weak monadic second-order logic
-
tree automata completion
-
first-order theory of rewriting
-
automata with constraints
-
tree set automata
-
tree transducers
Schedule
| week |
date |
topics |
slides |
exercises |
solutions |
|---|
| 01 |
07.10 |
finite word automata, terms |
pdf (1x1, 4x1) |
pdf |
pdf |
| 02 |
14.10 |
term rewriting, tree automata, regular
expressions |
pdf (1x1, 4x1) |
pdf |
pdf |
| 03 |
21.10 |
normal form automaton |
pdf (1x1, 4x1) |
pdf |
pdf |
| 04 |
28.10 |
homomorphisms, Myhill – Nerode relations,
minimization |
pdf (1x1, 4x1) |
pdf |
pdf |
| 05 |
04.11 |
normalization, regularity preservation,
tree automata completion |
pdf (1x1, 4x1) |
pdf |
pdf |
| 06 |
11.11 |
match-bounds |
pdf (1x1, 4x1) |
pdf |
pdf |
| 07 |
18.11 |
regularity preservation, call-by-need
strategies |
pdf (1x1, 4x1) |
pdf |
pdf |
| 08 |
25.11 |
regularity preservation, dependency
graph approximations |
pdf (1x1, 4x1) |
pdf |
pdf |
| 09 |
02.12 |
minimization, regular relations |
pdf (1x1, 4x1) |
pdf |
pdf |
| 10 |
09.12 |
GTT relations |
pdf (1x1, 4x1) |
pdf |
pdf |
| 11 |
16.12 |
anchored GTT relations, first-order
theory of rewriting |
pdf (1x1, 4x1) |
pdf |
pdf |
| 12 |
13.01 |
infinity predicate, synthesis, non-ground
terms |
pdf (1x1, 4x1) |
pdf |
pdf |
| 13 |
20.01 |
undecidability, formalization, certification |
pdf (1x1, 4x1) |
|
|
|
27.01 |
test
(solution) |
|
|
|
Literature
Slides and solutions to selected exercises will be made available online.
Accompanying literature will be provided.