The bideterministic concatenation product
Pin, Jean-Eric ; Thérien, Denis
HAL, hal-00020072 / Harvested from HAL
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.
Publié le : 1993-07-05
Classification:  concatenation product,  formal languages,  finite semigroups,  MR 20M35 (20M07 68Q70),  [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR],  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
@article{hal-00020072,
     author = {Pin, Jean-Eric and Th\'erien, Denis},
     title = {The bideterministic concatenation product},
     journal = {HAL},
     volume = {1993},
     number = {0},
     year = {1993},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00020072}
}
Pin, Jean-Eric; Thérien, Denis. The bideterministic concatenation product. HAL, Tome 1993 (1993) no. 0, . http://gdmltest.u-ga.fr/item/hal-00020072/