IFIP Logo
Sign in for Members and Observers

IFIP WG1.3 Foundations of System Specification


Talk "From Thin Trees to Thin Coalgebras"

by Corina Cirstea

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.