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}, publisher = {EDP-Sciences}, volume = {35}, number = {6}, year = {2001}, doi = {10.1051/ita:2001134}, mrnumber = {1922298}, zbl = {1011.20054}, language = {en}, url = {http://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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, Volume 35 (2001) no. 6, pp. 597-618. doi : 10.1051/ita:2001134. http://archive.numdam.org/articles/10.1051/ita:2001134/
[1] Finite semigroups and universal algebra. Series in Algebra, Vol. 3. World Scientific, Singapore (1994). | MR | Zbl
,[2] Free profinite -trivial monoids. Int. J. Algebra Comput. 7 (1997) 625-671. | MR | Zbl
and ,[3] Polynomial operations and rational languages, in 4th STACS. Springer, Lecture Notes in Comput. Sci. 247 (1987) 198-206. | MR | Zbl
,[4] Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91 (1991) 71-84. | MR | Zbl
,[5] On dot-depth two. RAIRO: Theoret. Informatics Appl. 24 (1990) 521-530. | EuDML | Numdam | Zbl
,[6] On a complete set of generators for dot-depth two. Discrete Appl. Math. 50 (1994) 1-25. | Zbl
,[7] Hierarchies of aperiodic languages. RAIRO Theoret. Informatics. Appl. 10 (1976) 33-49. | EuDML | Numdam | MR
,[8] The dot-depth hierarchy of star-free languages is infinite. J. Comput. System Sci. 16 (1978) 37-55. | MR | Zbl
and ,[9] Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math. 6 (1960) 66-92. | MR | Zbl
,[10] AUTOMATE, a computing package for automata and finite semigroups. J. Symb. Comput. 12 (1991) 197-220. | MR | Zbl
and ,[11] Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1-15. | MR | Zbl
and ,[12] Inverse monoids of dot-depth . Int. J. Algebra and Comput. 3 (1993) 411-424. | MR | Zbl
,[13] Automata, languages and machines, Vol. B. Academic Press, New York (1976). | MR | Zbl
.[14] Algorithms for computing finite semigroups, in Foundations of Computational Mathematics, edited by F. Cucker and M. Shub. Springer, Berlin (1997) 112-126. | MR | Zbl
and ,[15] Languages of dot-depth 3/2, in Proc. 17th Symposium on Theoretical Aspects of Computer Science. Springer, Lecture Notes in Comput. Sci. 1770 (2000) 555-566. | MR | Zbl
and ,[16] Decidable Hierarchies of Starfree Languages, in Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Springer, Lecture Notes in Comput. Sci. 1974 (2000) 503-515. | MR | Zbl
and ,[17] Concatenation Hierarchies and Forbidden Patterns, Technical Report No. 256. University of Wuerzburg (2000).
and ,[18] Level of the Straubing-Thérien hierarchy for two-letter alphabets (to appear). | Zbl
and ,[19] On radical congruence systems. Semigroup Forum 59 (1999) 56-73. | MR | Zbl
and ,[20] Ash's Type II Theorem, Profinite Topology and Malcev Products. Int. J. Algebra and Comput. 1 (1991) 411-436. | Zbl
, , and ,[21] A semigroup characterization of dot-depth one languages. RAIRO: Theoret. Informatics Appl. 17 (1983) 321-330. | Numdam | MR | Zbl
,[22] Some theorems on graph congruences. RAIRO: Theoret. Informatics Appl. 17 (1983) 331-342. | Numdam | MR
,[23] Counter-free Automata. MIT Press (1971). | MR | Zbl
and ,[24] Product of group languages, in FCT Conference. Springer, Lecture Notes in Comput. Sci. 199 (1985) 285-299. | MR | Zbl
and ,[25] Power semigroups and polynomial closure, in Proc. of the Third International Colloquium on Words, Languages and Combinatorics (to appear). | MR
and ,[26] Hiérarchies de concaténation. RAIRO: Theoret. Informatics Appl. 18 (1984) 23-46. | Numdam | MR | Zbl
,[27] Variétés de langages formels. Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986). | MR | Zbl
,[28] A property of the Schützenberger product. Semigroup Forum 35 (1987) 53-62. | MR | Zbl
,[29] A variety theorem without complementation. Izvestiya VUZ Matematika 39 (1995) 80-90. English version, Russian Mathem. (Iz. VUZ) 39 (1995) 74-83. | MR | Zbl
,[30] Syntactic semigroups, Chap. 10, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa. Springer (1997). | MR
,[31] Bridges for concatenation hierarchies, in 25th ICALP. Springer, Berlin, Lecture Notes in Comput. Sci. 1443 (1998) 431-442. | MR | Zbl
,[32] Algebraic tools for the concatenation product. Theoret. Comput. Sci. (to appear). | MR | Zbl
,[33] Monoids of upper triangular matrices. Colloq. Math. Soc. János Bolyai 39 (1981) 259-272. | MR | Zbl
and ,[34] A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis 35 (1996) 577-595. | MR | Zbl
and ,[35] Profinite semigroups, Mal'cev products and identities. J. Algebra 182 (1996) 604-626. | Zbl
& ,[36] Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 1-39. | MR | Zbl
and ,[37] The wreath product principle for ordered semigroups. Comm. in Algebra (to appear). | MR | Zbl
and ,[38] On finite monoids having only trivial subgroups. Inform. and Control 8 (1965) 190-194. | MR | Zbl
,[39] A logical approach to decidability of hierarchies of regular star-free languages, in Proc. STACS 2001. Springer, Lecture Notes in Comput. Sci. 2010 (2001) 539-550. | MR | Zbl
,[40] Piecewise testable events, in Proc. 2nd GI Conf. Springer, Lecture Notes in Comput. Sci. 33 (1975) 214-222. | MR | Zbl
,[41] Polynomial closure and topology. Int. J. Algebra and Comput. 10 (2000) 603-624. | MR | Zbl
,[42] Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra 15 (1979) 319-327. | MR | Zbl
,[43] A generalization of the Schützenberger product of finite monoids. Theory Comput. Systems 13 (1981) 137-150. | MR | Zbl
,[44] Relational morphisms and operations on recognizable sets. RAIRO: Theoret. Informatics Appl. 15 (1981) 149-159. | Numdam | MR | Zbl
,[45] Finite semigroups varieties of the form . J. Pure Appl. Algebra 36 (1985) 53-94. | MR | Zbl
,[46] Semigroups and languages of dot-depth two. Theoret. Comput. Sci. 58 (1988) 361-378. | MR | Zbl
.[47] On a conjecture concerning dot-depth two languages. Theoret. Comput. Sci. 104 (1992) 161-183. | MR | Zbl
and ,[48] Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. | MR | Zbl
,[49] Classifying regular events in symbolic logic. J. Comput. Syst. Sci. 25 (1982) 360-375. | MR | Zbl
,[50] An application of the Ehrenfeucht-Fraïssé game in formal language theory. Bull. Soc. Math. France 16 (1984) 11-21. | Numdam | Zbl
,[51] A concatenation game and the dot-depth hierarchy, in Computation Theory and Logic, edited by E. Böger. Springer, Lecture Notes in Comput. Sci. 270 (1987) 415-426. | MR | Zbl
,[52] The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Universalis 37 (1997) 491-526. | MR | Zbl
& ,[53] Inverse monoids of dot-depth two. Theoret. Comput. Sci. 66 (1989) 233-245. | MR | Zbl
,[54] Some results on the dot-depth hierarchy. Semigroup Forum 46 (1993) 352-370. | MR | Zbl
,Cited by Sources: