A conjecture on the concatenation product

¹ LIAFA, Université Paris VII et CNRS, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; (Jean-Eric.Pin@liafa.jussieu.fr)
² LaBRI, Université Bordeaux I et CNRS, 351 cours de la Libération, 33405 Talence Cedex, France; (Pascal.Weil@labri.fr)

Received: July 2001
Received: March 2002

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 and some supporting evidence for that new formulation. 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.