The Power-Set Construction for Tree Algebras

Abstract

We study power-set operations on classes of trees and tree algebras. Our main result consists of a distributive law between the tree monad and the upwards-closed power-set monad, in the case where all trees are assumed to be linear. For non-linear ones, we prove that such a distributive law does not exist.

References in corpus (2)

• Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic
• Algebraic Language Theory for Eilenberg--Moore Algebras