Catalan monoids, monoids of local endomorphisms, and their presentations
Research Report 95-6
Date: February 1995, revised 7 August 1995
The Catalan monoid and partial Catalan monoid of a directed graph are
introduced. Also introduced is the notion of a local endomorphism of a tree,
and it is shown that the Catalan (resp. partial Catalan) monoid of a tree is
simply 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 Popova which give presentations for the
Catalan monoid and partial Catalan monoid of a finite symmetric chain.
semigroup. monoid. graph. tree. local-endomorphism.
AMS Subject Classification (1991)
The paper is available in the following forms:
- cat-mon-end.ps.gz (82kB) or
To minimize network load, please choose the smaller gzipped .gz form if
and only if your browser client supports it.
Sydney Mathematics and Statistics