First-order tree-to-tree functions

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.

Authors

• Amina Doumane.

Keywords

No keywords are indexed for this paper.