The Catalan monoid and partial Catalan monoid of a directed graph are introduced. Also introduced is the notion of a local endomorphiam of a tree, and it is shown that the Catalan (resp. partial Catalan) monoid of a tree is aimply its monoid of extensive local endomorphisms (resp. partial endomorphisms) of finite shift. The main results of this paper are presentations for the Catalan and partial Catalan monoids of a tree. Our presentation for the Catalan monoid of a tree is used to give an alternative proof for a result of Higgins. We also identify results of Aizenstat and Popoya which give presentations for the Catalan monoid and partial Catalan monoid of a finite symmetric chain.
展开▼