Actions, Wreath Products of
C-varieties and Concatenation Product.
Laura Chaubard, Jean-Éric Pin et Howard Straubing
Résumé : Les C-variétés, introduites par le troisième
auteur étendent le champ d'application des variétés d'Eilenberg à de
nouvelles classes de langages. Dans cet article, nous commençons par
définir les C-variétés d'action, qui sont proches des automates et nous
prouvons leur équivalence avec la définition originale des C-variétés de
timbres. Ensuite, nous complétons l'étude du produit en couronne initiée
par Ésik et Ito en étendant sa définition aux C-variétés de deux façons
différentes, dont on montre qu'elles sont équivalentes. Nous énonçons
également une extension du principe du produit en couronne, un outil
standard de la théorie des langages. Finalement, notre résultat principal
généralise aux C-variétés la caractérisation algébrique de la clôture par
produit d'une variété de langages.
Abstract : The framework of C-varieties, introduced by the
third author, extends the scope of Eilenberg's variety theory to new
classes of languages. In this paper, we first define C-varieties of
actions, which are closely related to automata, and prove their equivalence
with the original definition of C-varieties of stamps. Next, we
complete the study of the wreath product initiated by Ésik and Ito by
extending its definition to C-varieties in two different ways, which
are proved to be equivalent. We also state an extension of the wreath
product principle, a standard tool of language theory. Finally, our main
result generalizes to C-varieties the algebraic characterization of
the closure under product of a variety of languages.