First-order tree-to-tree functions

Mikołaj Bojańczyk, Amina Doumane

We study tree-to-tree transformations that can be defined in first-order logic or monadic second-order logic. We prove a decomposition theorem, which shows that every transformatio…