Speaker
Bartek Klin, University of Oxford
Title
Polyregular Functions on Trees of Bounded Height
Abstract
We consider first-order interpretations that input and output unordered trees of bounded height. We prove that the equivalence problem for such functions is decidable, i.e. given two such interpretations, one can decide whether for every input tree, the two output trees are isomorphic.
We also give a calculus, based on prime functions and combinators, which derives all first-order inter- pretations for unordered trees of bounded height. The calculus is based on a type system, where the type constructors are products, co-products and a multiset monad, all interpreted in a category of structure classes and first-order interpretations.
This is joint work with Mikolaj Bojanczyk.
