Issue Theoret. Informatics Appl. Volume 35, Number 6, November-December 2001 A tribute to Aldo de Luca Page(s) 597 - 618 DOI 10.1051/ita:2001134

DOI: 10.1051/ita:2001134


Theoret. Informatics Appl. 35, 597-618 (2001)

A conjecture on the concatenation product

Jean-Eric Pin¹ and Pascal Weil<sup>2

1</sup>  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. Revised 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.

Mathematics Subject Classification. 20M07, 68Q45, 20M35


© EDP Sciences 2001

What is OpenURL?