The bideterministic concatenation product

Jean-Éric Pin et Denis Thérien



Résumé : Cet article est consacré à l'étude du produit de concaténation bidéterministe, une variante du produit de concaténation. Nous donnons une caractérisation algébrique des variétés de langages fermées pour ce produit. Plus précisément, soit V une variété de monoïdes, soit V la variété de langages correspondante et soit W la plus petite variété contenant V et le produit bidéterministe de deux langages quelconques de V. On donne une description algébrique de la variété de monoïdes W correspondant à W. Par exemple, nous calculons W lorsque V est l'une des variétés suivantes: la variété des monoïdes idempotents et commutatifs, la variété des monoïdes qui sont des demi-treillis de groupes d'une variété de groupes donnée, la variété des monoïdes idempotents et R-triviaux. En particulier, nous montrons que la plus petite variété de langages fermée par produit bidéterministe et contenant le langage {1} correspond à la variété des monoïdes J-triviaux dont les idempotents commutent. On connaissait déjà des résultats similaires pour d'autres variantes du produit de concaténation, mais les opérations algébriques correspondantes utilisaient des variantes du produit semidirect et du produit de Malcev. Ici, l'opération V -> W repose sur la construction d'une expansion, qui associe à chaque monoïde fini M un monoïde fini N possédant les propriétés suivantes:
  1. M est un quotient de N,
  2. le morphisme f : N -> M induit un isomorphisme entre les sous-monoïdes de N et de M engendrés par leurs éléments réguliers respectifs
  3. l'image inverse d'un idempotent de M par f est un semigroupe 2-nilpotent.



Abstract : This paper is devoted to the study of the bideterministic concatenation product, a variant of the concatenation product. We give an algebraic characterization of the varieties of languages closed under this product. More precisely, let V be a variety of monoids, V the corresponding variety of languages and W the smallest variety containing V and the bideterministic products of two languages of V. We give an algebraic description of the variety of monoids W corresponding to W. For instance, we compute W when V is one of the following varieties : the variety of idempotent and commutative monoids, the variety of monoids which are semilattices of groups of a given variety of groups, the variety of R-trivial and idempotent monoids. In particular, we show that the smallest variety of languages closed under bideterministic product and containing the language {1}, corresponds to the variety of J-trivial monoids with commuting idempotents. Similar results were known for the other variants of the concatenation product, but the corresponding algebraic operations on varieties of monoids were based on variants of the semidirect product and of the Malcev product. Here the operation V -> W makes use of a construction which associates to any finite monoid M an expansion N, with the following properties:
  1. M is a quotient of N,
  2. the morphism f : N -> M induces an isomorphism between the submonoids of N and of M generated by the regular elements and
  3. the inverse image under f of an idempotent of M is a 2-nilpotent semigroup.


PostScript file compressed with gzip, PDF file


Valid HTML 4.01!