Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Tree automata and applications (24h, 4 ECTS)

Teachers:

  • Laurent Doyen (lecture and exercices)

Time/location: Tuesdays, 8:30–12:45. Cachan room Cournot C321

Planned Contents

The course introduces a generalisation of finite automata to finite trees. Tree automata provide an algorithmic toolbox for reasoning about infinite sets of trees, allowing in particular to solve formal logic problems. They have concrete applications, for instance in XML processing and modelling in computational linguistics.

The course assumes good familiarity with finite automata running over finite words and with basic concepts from complexity theory.

  • basics: trees, terms, contexts
  • finite tree automata: top-down versus bottom-up, closure properties
  • decision problems, complexity
  • monadic second order logic
  • unranked trees
  • alternation
  • navigation

Resources

Teaching language policy

English upon request

Prerequisites

  • Finite (word) automata and context-free grammars.
  • Basic notions of complexity: the classes NL, P, NP, PSPACE, EXPTIME.
  • Basic notions of first-order logic.

Related Courses

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA