Résumé : Dans un article antérieur, les auteurs
avaient étudié la fermeture polynomiale d'une
variété de langages et avaient donné la contrepartie
algébrique, en termes de produit de Mal'cev, de cette
opération. Nous avions aussi formulé une conjecture sur la
contrepartie algébrique de la fermeture booléenne de la
fermeture polynomiale --- cette opération est celle qui permet de
monter d'un niveau dans chaque hiérarchie de concaténation
---. Bien que cette conjecture soit probablement vraie dans quelques cas
particuliers, nous en donnons un contre-exemple dans le cas
général. Un autre contre-exemple, de nature
différente, a été trouvé récemment par
Steinberg. Tenant compte de ces deux exemples, nous proposons une version
modifiée de notre conjecture. Nous montrons en particulier que la
solution de notre nouvelle conjecture donnerait une solution au
problème de la décidabilité des niveaux 2 des
hiérarchies de Straubing-Thérien et de la hiérarchie
"dot-depth". Nous discutons également des conséquences pour
les autres niveaux.
Abstract : In a previous paper, the authors studied the polynomial
closure of a variety of languages and gave an algebraic counterpart, in
terms of Mal'cev products, of this operation. They also formulated a
conjecture about the algebraic counterpart of the boolean closure of the
polynomial closure --- this operation corresponds to passing to the upper
level in any concatenation hierarchy ---. Although this conjecture is
probably true in some particular cases, we give a counterexample in the
general case. Another counterexample, of a different nature, was
independently given recently by Steinberg. Taking these two
counterexamples into account, we propose a modified version of our
conjecture. We show in particular that a solution to our new conjecture
would give a solution of the decidability of the levels 2 of the
Straubing-Thérien hierarchy and of the dot-depth hierarchy.
Consequences for the other levels are also discussed.