Notes
Slide Show
Outline
1
Tree Transducers and their Applications to XML
  • Tarragona Lectures
  • 22-26.3.2004


  • Sebastian Maneth
  • Swiss Inst. of Technology, Lausanne
  • Sebastian.Maneth@epfl.ch
2
Overview



  • 1st  Day:     History of Tree Transducers, Finite-State Models


  • 2nd Day:     Context-Free Models


  • 3rd Day:      Properties of Macro Tree Tranducers


  • 4th Day:      XML Type Checking using MTTs


  • TODAY:     Complexity of MTTs
3
Today



  • 1.   Complexity of Macro Tree Transducers


  • 2.   MSO Definability and Linear Size Increase


  • 3.   Open Problems in Tree Transducer Theory
4
1. Complexity of MTTs
5
1. Complexity of MTTs
6
1. Complexity of MTTs
7
Complexity of Tree Transducers
8
Complexity of Tree Transducers
9
Complexity of Tree Transducers
10
Complexity of Tree Transducers
11
Complexity of Tree Transducers
12
Complexity of Tree Transducers
13
Complexity of Tree Transducers
14
Complexity of Tree Transducers
15
Complexity of Tree Transducers
16
Decomposition of MTT
17
Decomposition of MTT
18
Decomposition of MTT
19
Decomposition of MTT
20
 
21
 
22
 
23
 
24
 
25
 
26
 
27
 
28
EXERCISES
29
Complexity of MTTs
30
Removal of Input Deletion
31
Removal of Parameter Deletion
32
Removal of Parameter Deletion
33
Removal of Deletion
34
No Deletion and No Skipping
35
Translation Problem
36
Translation Problem
37
Translation Problem
38
Translation Problem
39
Translation Problem
40
2. MSO Definability
41
2. MSO Definability
42
 
43
 
44
 
45
2. MSO Definability
46
Size Increases
47
2. MSO Definability
48
2. MSO Definability
49
2. MSO Definability
50
2. MSO Definability
51
2. MSO Definability
52
2. MSO Definability
53
2. MSO Definability
54
3.  Open Problems in Tree Transducer Theory