Chairs: C. Cirstea, F. Gadducci, H. Schlingloff Past Chairmen: M. Roggenbach, L. Schröder, T. Mossakowski, J. Fiadeiro, P. Mosses, H.-J. Kreowski
Fri, 01 November 2024 at 05:15 pm in Crete, Greece
Joint work with: Anton Chernev, Alexandre Goy, Helle Hvid Hansen, Clemens Kupke
Abstract: Infinite trees with countably many infinite branches, called thin trees, have been studied via methods from descriptive set theory, automata theory and algebra. We take a categorical approach to trees as the behaviours of coalgebras for a polynomial functor, and introduce syntactic representatives of thin trees via an initial algebra for a functor. Our central technical result is a characterisation of thin trees as the quotient of this initial algebra by a certain equation. To obtain this result, we prove that the trees which admit a representative are precisely the thin ones, and that each thin tree has a canonical representative to which all other representatives are equivalent. We use our categorical characterisation of thin trees to generalise the notion of thinness from trees to coalgebras. Finally, we give a syntactic definition of the rank of a thin tree, and show that this coincides with the notion of Cantor-Bendixson rank from descriptive set theory.