Polyregular functions on unordered trees of bounded height

Mikołaj Bojańczyk, Bartek Klin

We consider injective first-order interpretations that input and output trees of bounded height. The corresponding functions have polynomial output size, since a first-order interp…