Upper set monoids and length preserving morphisms.

Upper set monoids and length preserving morphisms.

Antonio Cano and Jean-Éric Pin

Résumé : Les morphismes alphabétiques et les inverses de substitution sont deux opérations bien connues sur les langages rationnels. Leur lien avec les variétés engendrées par les monoïdes de parties a été établi indépendamment par Reutenauer et par Straubing en 1979. Plus récemment, une version ordonnée de cette théorie a été proposée par Polák et par les auteurs. Dans cet article, nous présentons une version améliorée de ces résultats dont nous obtenons les conséquences suivantes. Étant donné une variété de monoïdes ordonnés finis V, soit P^↑V la variété de monoïdes ordonnés finis engendrée par les monoïdes des parties closes par le haut des membres de V. Alors P^↑(P^↑V) = P^↑V. Ce résultat fait contraste avec les résultats connus dans le cas non ordonné: l'opérateur PV correspondant au monoïde des parties satisfait P³V = P⁴V, mais les variétés V, PV, P²V et P³V peuvent être distinctes.

Abstract : Length preserving morphisms and inverse of substitutions are two well-studied operations on regular languages. Their connection with varieties generated by power monoids was established independently by Reutenauer and Straubing in 1979. More recently, an ordered version of this theory was proposed by Polák and by the authors. In this paper, we present an improved version of these results and obtain the following consequences. Given a variety of finite ordered monoids V, let P^↑V be the variety of finite ordered monoids generated by the upper set monoids of members of V. Then P^↑(P^↑V) = P^↑V. This contrasts with the known results for the unordered case: the operator PV corresponding to power monoids satisfies P³V = P⁴V, but the varieties V, PV, P²V and P³V can be distinct.

PDF file