Table of Contents
## Tree automata and applications (24h, 3 ECTS)Teachers: - Sylvain Schmitz (lectures)
- Charlie Jacomme (exercises)
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. - 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
## 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.
- homework assignment, due on Nov. 2, 2018: Tree Transducers
- exam on Nov. 6, 2018 at 9:30am
- homework assignment, due on Oct. 10, 2017: Courcelle's Theorem
- exam on Nov. 7, 2017: exam
- homework assignment, due on Oct. 21, 2016: Residual Tree Languages
- exam on Nov. 4, 2016: exam
- first exercise sheet: TD1: recognisable tree languages and tree automata
- second exercise sheet: TD2: decision problems and tree homomorphisms
- third exercise sheet: TD3: WSkS
- fourth exercise sheet: TD4: hedge automata, alternating word automata, and membership
- fifth exercise sheet: TD5: PDL and document type definitions
## Teaching language policyEnglish 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 |