The poset of retracts of a free monoid

Abstract

The set of retracts of a free monoid F with the partial order of inclusion is investigated. This poset is a lattice if and only if F is generated by three or fewer elements. For a finitely generated free monoid F it is shown non-constructively that, for every submonoid S of F, the intersection of all retracts of F containing S is regular. A regular expression can be constructed for this intersection when S is regular. The submonoid generated by the set of all retracts of F contained in the regular submonoid S is also regular and constructable. This allows the decision to be made whether or not any given pair of retracts has a supremum or an infimum in the poset of retracts of F. The procedure yields regular expressions for such suprema and infima when they exist.

Keywords:

• Retracts
• codes
• languages
• monoids
• semigroups

C.R. Categories:

• F.4 (Formal Langs)