On second-order iterative monads

B. Courcelle studied algebraic trees as precisely the solutions of all recursive program schemes for a given signature in Set. He proved that the corresponding monad is iterative. We generalize this to recursive program schemes over a given finitary endofunctor H of a “suitable” category. A monad is called second-order iterative if every guarded recursive program scheme has a unique solution in it. We construct two second-order iterative monads: one, called the second-order rational monad, S H, is proved to be the initial second-order iterative monad. The other one, called the context-free monad, C H, is a quotient of S H and in the original case of a polynomial endofunctor H of Set we prove that C H is the monad studied by B. Courcelle. The question whether these two monads are equal is left open.

Authors

• Jiří Adámek
• Stefan Milius
• Jiří Velebil

Keywords

• Algebraic trees
• Recursive program schemes
• Ideal theory
• Monads