Table of Contents
Tree automata and applications (24h, 4 ECTS)Teachers:
Time/location: Tuesdays, 8:30–12:45. Cachan room Cournot C321 Planned ContentsThe 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.
ResourcesA large part of the lectures is covered by TATA, notably Chapters 1, 3, and 8; here is a summary of the basic definitions for logics on finite trees, and here is a good article on PDL for ordered trees; see also this article for the translation to 2AFTA. For 2018–2019:
For 2017–2018:
For 2016–2017:
Teaching language policyEnglish upon request Prerequisites
Related Courses |