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.
@article{ITA_2001__35_6_597_0,
author = {Pin, Jean-Eric and Weil, Pascal},
title = {A conjecture on the concatenation product},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {597--618},
year = {2001},
publisher = {EDP-Sciences},
volume = {35},
number = {6},
doi = {10.1051/ita:2001134},
mrnumber = {1922298},
zbl = {1011.20054},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2001134/}
}
TY - JOUR AU - Pin, Jean-Eric AU - Weil, Pascal TI - A conjecture on the concatenation product JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2001 SP - 597 EP - 618 VL - 35 IS - 6 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2001134/ DO - 10.1051/ita:2001134 LA - en ID - ITA_2001__35_6_597_0 ER -
%0 Journal Article %A Pin, Jean-Eric %A Weil, Pascal %T A conjecture on the concatenation product %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2001 %P 597-618 %V 35 %N 6 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2001134/ %R 10.1051/ita:2001134 %G en %F ITA_2001__35_6_597_0
Pin, Jean-Eric; Weil, Pascal. A conjecture on the concatenation product. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 597-618. doi: 10.1051/ita:2001134
Cité par Sources :