Highlights Conference 2019 Conference Abstract
First-order tree-to-tree functions
- Amina Doumane.
We define a class of functions, called first-order tree-to-tree functions, which manipulates objects such as trees, trees of trees, pairs of trees, etc. The definition is in the style of regular expressions: we start with some basic functions, and more complex functions are constructed using some combinators (most importantly, composition). Our main result is that first-order tree-to-tree functions are exactly the same as first-order tree-to-tree transductions.