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 1^st Day: History of Tree Transducers, Finite-State Models TODAY: Context-Free Models 3^rd Day: Properties of Macro Tree Trandsucers 4^th Day: XML Type Checking using MTTs 5^th Day: Complexity of MTTs
3	Today 1. Limits of Top-Down Tree Transducers 2. More Powerful Models 3. Context-Free Tree Grammars 4. Macro Tree Transducers
4	1. Limits of Top-Down Tr. Tr.s
5	1. Limits of Top-Down Tr. Tr.s
6	1. Limits of Top-Down Tr. Tr.s
7	1. Limits of Top-Down Tr. Tr.s
8	1. Limits of Top-Down Tr. Tr.s
9	1. Limits of Top-Down Tr. Tr.s
10	1. Limits of Top-Down Tr. Tr.s
11	1. Limits of Top-Down Tr. Tr.s
12	1. Limits of Top-Down Tr. Tr.s
13	1. Limits of Top-Down Tr. Tr.s
14	1. Limits of Top-Down Tr. Tr.s
15	1. Limits of Top-Down Tr. Tr.s
16	1. Limits of Top-Down Tr. Tr.s
17	1. Limits of Top-Down Tr. Tr.s
18	2. More Powerful Models
19	2. More Powerful Models
20	2. More Powerful Models
21	2. More Powerful Models
22	2. More Powerful Models
23	2. More Powerful Models
24	2. More Powerful Models
25	2. More Powerful Models
26	2. More Powerful Models
27	2. More Powerful Models
28	2. More Powerful Models
29	2. More Powerful Models
30	2. More Powerful Models
31	2. More Powerful Models
32	2. More Powerful Models
33	Attributed Tree Transducers
34	Attributed Tree Transducers
35	Even more powerful:
36	Even more powerful:
37	The k-Pebble Tree Transducer
38	Why Pebbles?
39	Pebbles in Automata Theory
40	Pebbles and XML Qu. Langs
41	Pebbles and XML Qu. Langs
42	Pebbles and XML Qu. Langs
43	3. Context-Free Tree Grammars
44	3. Context-Free Tree Grammars
45	3. Context-Free Tree Grammars
46	3. Context-Free Tree Grammars
47	3. Context-Free Tree Grammars
48	3. Context-Free Tree Grammars
49	3. Context-Free Tree Grammars
50	3. Context-Free Tree Grammars
51	3. Context-Free Tree Grammars
52	3. Context-Free Tree Grammars
53	3. Context-Free Tree Grammars
54	3. Context-Free Tree Grammars
55	3. Context-Free Tree Grammars
56	3. Context-Free Tree Grammars
57	3. Context-Free Tree Grammars
58	3. Context-Free Tree Grammars
59	3. Context-Free Tree Grammars
60	3. Context-Free Tree Grammars
61	3. Context-Free Tree Grammars
62	3. Context-Free Tree Grammars
63	3. Context-Free Tree Grammars
64	3. Context-Free Tree Grammars
65	3. Context-Free Tree Grammars
66	3. Context-Free Tree Grammars
67	3. Context-Free Tree Grammars
68	OI and IO derivations
69	OI and IO derivations
70	OI and IO derivations
71	OI and IO derivations
72	OI and IO derivations
73	OI and IO derivations
74	OI and IO derivations
75	OI and IO derivations
76	OI and IO derivations
77	OI and IO derivations
78	OI and IO derivations
79	Context-Free Tree Grammars
80	OI (lazy) = unrestricted
81
82
83
84
85
86
87
88
89
90
91
92
93
94	CF Tree Languages
95	CF Tree Languages
96	4. Macro Tree Transducers
97	4. Macro Tree Transducers
98	4. Macro Tree Transducers
99	4. Macro Tree Transducers