The Power-Set Construction for Tree Algebras

DOI10.46298/LMCS-19(4:9)2023MaRDI QIDQ6178675zbMATH OpenOpenAlexFDO

Authors Achim Blumensath

Publication date 16 January 2024

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2207.00563

zbMATH Keywords

distributive lawpower-set functortree algebras

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

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.

Cites work

• Automata on finite trees
• Automata on infinite trees
• Automata, logics, and infinite games. A guide to current research
• Eilenberg Theorems for Free
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 7350772 (Why is no real title available?)
• scientific article; zbMATH DE number 3296291 (Why is no real title available?)
• Monad compositions II: Kleisli strength
• Monad compositions. I: General constructions and recursive distributive laws
• No-go theorems for distributive laws
• On finite monoids having only trivial subgroups
• Regular matching problems for infinite trees
• Regular tree algebras
• The Vietoris monad and weak distributive laws
• Trace semantics for coalgebras

Cited in

(2)

• The expansion problem for infinite trees
• The structures of full terms preserving a partition under different operations

This page was built for publication: The Power-Set Construction for Tree Algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178675)