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 2^nd Day: Context-Free Models TODAY: Properties of Macro Tree Tranducers 4^th Day: XML Type Checking using MTTs 5^th Day: Complexity of MTTs
3	Today 1. Expressive Power of Macro Tree Transducers 2. Closure under regular look-ahead 3. Inverses of MTTs preserve REGT
4	Macro Tree Transducer
5	Macro Tree Transducer
6	Macro Tree Transducer
7	Macro Tree Transducer
8	Macro Tree Transducer
9	Macro Tree Transducer
10	Macro Tree Transducer
11	Macro Tree Transducer
12	Macro Tree Transducer
13	OI vs. IO
14	1. Expressive Power of MTTs
15	1. Expressive Power of MTTs
16	1. Expressive Power of MTTs
17	1. Expressive Power of MTTs
18	1. Expressive Power of MTTs
19	1. Expressive Power of MTTs
20	1. Expressive Power of MTTs
21	1. Expressive Power of MTTs
22	1. Expressive Power of MTTs
23	1. Expressive Power of MTTs
24	1. Expressive Power of MTTs
25	1. Expressive Power of MTTs
26	1. Expressive Power of MTTs
27	1. Expressive Power of MTTs
28	1. Expressive Power of MTTs
29	1. Expressive Power of MTTs
30	1. Expressive Power of MTTs
31	1. Expressive Power of MTTs
32	1. Expressive Power of MTTs
33	1. Expressive Power of MTTs
34	1. Expressive Power of MTTs
35	2. Closure under Reg. Look-Ah.
36	2. Closure under Reg. Look-Ah.
37	2. Closure under Reg. Look-Ah.
38	2. Closure under Reg. Look-Ah.
39	2. Closure under Reg. Look-Ah.
40	Example:
41	Example:
42	Example:
43	Example:
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60	2. Closure under Reg. Look-Ah.
61	3. Inverses of MTTs preserve REGT
62	3. Inverses of MTTs preserve REGT
63	3. Inverses of MTTs preserve REGT
64	3. Inverses of MTTs preserve REGT
65	3. Inverses of MTTs preserve REGT
66	3. Inverses of MTTs preserve REGT
67	3. Inverses of MTTs preserve REGT
68	3. Inverses of MTTs preserve REGT
69	3. Inverses of MTTs preserve REGT
70	3. Inverses of MTTs preserve REGT