Lectures

Logic and Automata

Canberra, Logic Summer School, December 2006

Lecture 1: Monadic Second-Order Logic on Graphs and Strings slides 6on1

  • 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 slides 6on1

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

    Lecture 3: Expressivness of MSO Graph Properties slides 6on1

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

    Lecture 4: Tree Automata, MSO-Translations slides 6on1

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

    Lecture 5: Properties of MSO Translations slides 6on1

  • 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 slides pdf-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 slides pdf-handout

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

    3rd Lecture: Properties of Macro Tree Transducers slides pdf-handout

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

    4th Lecture: XML Type Checking using MTTs slides pdf-handout

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

    5ht Lecture: Complexity of MTTs slides pdf-handout

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