First-order tree-to-tree functions

2020/02/21 by Bojańczyk, Mikołaj, Doumane, Amina
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2002.09307

Abstract

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 transformation can be obtained from prime transformations, such as tree-to-tree homomorphisms or pre-order traversal, by using combinators such as function composition.

Related

• Polyregular functions on unordered trees of bounded height
• Some connections between universal algebra and logics for trees
• On the nonexistence of FO-continuous path and tree-decompositions
• Rank-decreasing transductions
• On describing trees and quasi-trees from their leaves