Catalan monoids, monoids of local endomorphisms, and their presentations

Author

Andrew Solomon

Status

Research Report 95-6
Date: February 1995, revised 7 August 1995

Abstract

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.

Key phrases

semigroup. monoid. graph. tree. local-endomorphism.

AMS Subject Classification (1991)

Primary:
Secondary:

Content

The paper is available in the following forms:

PostScript:: cat-mon-end.ps.gz (82kB) or cat-mon-end.ps (268kB)

To minimize network load, please choose the smaller gzipped .gz form if and only if your browser client supports it.

Sydney Mathematics and Statistics