×

The poset of retracts of a free monoid. (English) Zbl 0723.68060

Summary: 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 finite 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 expressions 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.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1016/S0019-9958(77)90050-X · Zbl 0375.94022
[2] DOI: 10.1016/S0019-9958(79)90082-2 · Zbl 0422.68034
[3] DOI: 10.1080/00207169008803834 · Zbl 0825.68444
[4] Foryś W., Semigroup Forum
[5] DOI: 10.1080/00207168208803330 · Zbl 0496.68050
[6] Lallement G., Semigroups and Combinatorial Applications (1979)
[7] DOI: 10.1007/BF02570808 · Zbl 0261.20060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.