| Автор | Pin, Jean-Eric |
| Автор | Weil, Pascal |
| Дата выпуска | 2001 |
| dc.description | 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. |
| Формат | application.pdf |
| Издатель | EDP Sciences |
| Копирайт | © EDP Sciences, 2001 |
| Название | A conjecture on the concatenation product |
| Тип | research-article |
| DOI | 10.1051/ita:2001134 |
| Electronic ISSN | 1290-385X |
| Print ISSN | 0988-3754 |
| Журнал | RAIRO - Theoretical Informatics and Applications |
| Том | 35 |
| Первая страница | 597 |
| Последняя страница | 618 |
| Аффилиация | Pin Jean-Eric; LIAFA, Université Paris VII et CNRS, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; (Jean-Eric.Pin@liafa.jussieu.fr) |
| Аффилиация | Weil Pascal; LaBRI, Université Bordeaux I et CNRS, 351 cours de la Libération, 33405 Talence Cedex, France; (Pascal.Weil@labri.fr) |
| Выпуск | 6 |
