# Lectures

## Logic and Automata

### Canberra, Logic Summer School, December 2006

#### Lecture 1: Monadic Second-Order Logic on Graphs and Strings slides6on1

• Introduction to Monadic Second-Order Logic (MSO) on graphs
• Decidability Questions
• Introduction to Finite-State Automata

#### Lecture 2: Büchis Theorem, MSO on strings = Finite-State Automata slides6on1

• Finite-State Automata Recap
• Büchis Theorem
• MSO to automaton: non-elementary blow up

#### Lecture 3: Expressivness of MSO Graph Properties slides6on1

How to prove that something can NOT be expressed
• Pumping Lemma for regular languages
• Ehrenfeucht-Fraisse games

#### Lecture 4: Tree Automata, MSO-Translations slides6on1

• Automata from strings to trees
• Context-Free Sets
• MSO Definable Translations
• Applications

#### Lecture 5: Properties of MSO Translations slides6on1

• Composition Closure of MSOT
• Inverses of MSOT preserve MSO definability
• Parikhs Theorem
• Decidability of equivalence

## Tree Transducers and Applications to XML

### Tarragona, March 2004

#### 1st Lecture: History of Tree Transducers, Finite State Models slidespdf-handout

• History of Tree Transducers
• History of XML
• Trees and XML
• Tree Languages and XML Types
• From Languages to Translations

#### 2nd Lecture: Context-Free Models slidespdf-handout

• Limits of Top-Down Tree Transducers
• More Powerful Models
• Context-Free Tree Grammars
• Macro Tree Transducers

#### 3rd Lecture: Properties of Macro Tree Transducers slidespdf-handout

• Expressive Power of Macro Tree Transducers
• Closure under Regular Look Ahead
• Inverses of MTTs preserve REGT

#### 4th Lecture: XML Type Checking using MTTs slidespdf-handout

• XML Type Checking using MTTs
• Get the Complexity Down: COMPOSITION

#### 5ht Lecture: Complexity of MTTs slidespdf-handout

• Complexity of Macro Tree Transducers
• MSO Definabtility and Linear Size Increase
• Open Problems in Tree Transducer Theory