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



  • TODAY:    History of Tree Transducers, Finite-State Models


  • 2nd Day:    Context-Free Models


  • 3rd Day:    Properties of Macro Tree Transducers


  • 4th Day:    XML Type Checking using MTTs


  • 5th Day:    Complexity of MTTs
3
Today



  • 1.   History of Tree Transducers


  • 2.   History of XML


  • 3.   Trees and XML


  • 4.   Tree Languages and XML Types


  • 5.   From Languages to Translations
4
1. History of Tree Transducers
  • 1960 Irons, Syntax-Directed Compiler for  ALGOL 60
5
1. History of Tree Transducers
  • 1960 Irons, Syntax-Directed Compiler for  ALGOL 60
6
1. History of Tree Transducers
  • 1960 Irons, Syntax-Directed Compiler for  ALGOL 60
7
1. History of Tree Transducers
  • 1960 Irons, Syntax-Directed Compiler for  ALGOL 60
8
1. History of Tree Transducers
  • 1960 Irons, Syntax-Directed Compiler for  ALGOL 60
9
1. History of Tree Transducers
  • 1960  Irons, SD Translation


  • 1968  Knuth,  Attribute Grammar


  • 1970  Thatcher/Wright, Top-Down and Bottom-up Tr. Tr.s


  • 1980  Aho/Ullmann SD Trans. Schemes,
  •                                                     Tree Walking Transducers


  • 1985  Engelfriet/Vogler,  Macro Tree Transducer


  • 2000  Milo/Suciu/Vianu,  k-Pebble Tree Transducer
10
2. History of XML:  Why XML?
11
XML = Data
12
XML = Data + Structure
13
2. History of XML
14
Today: XML has many friends
  • Query Languages   Xpath, XSLT, XQuery, fxt, ..
  •                                                                (mostly by W3C)


  • Implementations  (Parsers, Validators, Translators):
  •                                     SAX, Xerces, Xalan, …
  •                            (by IBM/Apache, Microsoft, Oracle, Sun…)


  • Current Issues
  •     - PL/DB support  (“data binding”, JBind, Castor, Zeus …)
  •     - storage support  (compression, data optimization)
15
3. Trees
16
3. Trees
17
3. Trees in FL Theory
18
3. Trees in FL Theory
19
3. Trees in FL Theory
20
4. Tree Languages
21
Parse Trees
22
(Abstract) Parse Trees
23
(Abstract) Parse Trees
24
(Abstract) Parse Trees
25
(Abstract) Parse Trees
26
(Abstract) Parse Trees
27
(Abstract) Parse Trees
28
(Abstract) Parse Trees
29
(Abstract) Parse Trees
30
(Abstract) Parse Trees
31
(Abstract) Parse Trees
32
(Abstract) Parse Trees
33
(Abstract) Parse Trees
34
(Abstract) Parse Trees
35
Regular Tree Grammars
36
Regular Tree Grammars
37
Regular Tree Grammars
38
Context-Free Sets
39
Context-Free Sets
40
4. Regular Tree Languages
41
4. Regular Tree Languages
42
4. Regular Tree Languages
43
Automata:   From Strings to Trees
44
Automata:   From Strings to Trees
45
Automata:   From Strings to Trees
46
Automata:   From Strings to Trees
47
Automata:   From Strings to Trees
48
Automata:   From Strings to Trees
49
Automata:   From Strings to Trees
50
Automata:   From Strings to Trees
51
Automata:   From Strings to Trees
52
Automata:   From Strings to Trees
53
Automata:   From Strings to Trees
54
Automata:   From Strings to Trees
55
Automata:   From Strings to Trees
56
Automata:   From Strings to Trees
57
Automata:   From Strings to Trees
58
Automata:   From Strings to Trees
59
Automata:   From Strings to Trees
60
Top-Down Finite Tree Automata
61
Top-Down Finite Tree Automata
62
Bottom-Up Finite Tree Automata
63
Bottom-Up Finite Tree Automata
64
Bottom-Up Finite Tree Automata
65
Bottom-Up Finite Tree Automata
66
Bottom-Up Finite Tree Automata
67
5. From Languages to Translations
68
5. From Languages to Translations
69
5. From Languages to Translations
70
Translations
  • How to design formal models.
  • What do we want??
71
Translations
  • How to design formal models.
  • What do we want??
72
Transducers =
            Automata with Output
73
Transducers =
            Automata with Output
74
Transducers =
            Automata with Output
75
Top-Down Tree Transducer
76
Top-Down Tree Transducer
77
Top-Down Tree Transducer
78
Top-Down Tree Transducer
79
Top-Down Tree Transducer
80
Top-Down Tree Transducer
81
Top-Down Tree Transducer
82
Top-Down Tree Transducer
83
Top-Down Tree Transducer
84
Top-Down Tree Transducer
85
Top-Down Tree Transducer
86
Topics in Tree Transd. THEORY
  • Expressive Power


  • Closure Properties


  • Decidability Results


  • Complexity
87
Top-Down Tree Transducer
88
Applications of (1)
89
Applications of (1)
90
Applications of (1)
91
Top-Down Tree Transducer
92
Top-Down Tree Transducer
93
END of first lecture!
  • Problem to think of:


  • What is the  minimal DAG  of a tree t?


  • What is the minimal tree automaton
  •    accepting the language  { t }?