Article contents
A conjecture on the concatenation product
Published online by Cambridge University Press: 15 July 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.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 6: A tribute to Aldo de Luca , November 2001 , pp. 597 - 618
- Copyright
- © EDP Sciences, 2001
References
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20161010045618268-0270:S0988375401001345:S0988375401001345_eqnU1.gif?pub-status=live)
- 6
- Cited by