# Logic, Automata and Relations

## Contents

- Introduction
- Automata on tuples of finite trees
- Three notions of recognizability
- Examples of the three notions of recognizability
- Comparisons between the three classes
- Closure properties for
`Rec`

- Closure of GTT by composition and iteration
- The logic WSkS
- Syntax
- Semantics
- Examples
- Restricting the syntax
- Definable sets are recognizable sets
- Recognizable sets are definable
- Complexity issues
- Extensions
- Examples of applications
- Terms and sorts
- The encompassment theory for linear terms
- The first-order theory of a reduction relation: the case where no variables are shared
- Reduction strategies
- Application to higher-order matching
- Exercises
- Bibliographic Notes
- Automata and Logic
- Surveys