A conjecture on the concatenation product

Pin, Jean-Eric; Weil, Pascal

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 597-618

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.

Classification : 20M07, 68Q45, 20M35

[1] J. Almeida, Finite semigroups and universal algebra. Series in Algebra, Vol. 3. World Scientific, Singapore (1994). | Zbl | MR

[2] J. Almeida and P. Weil, Free profinite $ℛ$-trivial monoids. Int. J. Algebra Comput. 7 (1997) 625-671. | Zbl | MR

[3] M. Arfi, Polynomial operations and rational languages, in 4th STACS. Springer, Lecture Notes in Comput. Sci. 247 (1987) 198-206. | Zbl | MR

[4] M. Arfi, Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91 (1991) 71-84. | Zbl | MR

[5] F. Blanchet-Sadri, On dot-depth two. RAIRO: Theoret. Informatics Appl. 24 (1990) 521-530. | Numdam | Zbl | EuDML

[6] F. Blanchet-Sadri, On a complete set of generators for dot-depth two. Discrete Appl. Math. 50 (1994) 1-25. | Zbl

[7] J.A. Brzozowski, Hierarchies of aperiodic languages. RAIRO Theoret. Informatics. Appl. 10 (1976) 33-49. | Numdam | MR | EuDML

[8] J.A. Brzozowski and R. Knast, The dot-depth hierarchy of star-free languages is infinite. J. Comput. System Sci. 16 (1978) 37-55. | Zbl | MR

[9] J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math. 6 (1960) 66-92. | Zbl | MR

[10] J.M. Champarnaud and G. Hansel, AUTOMATE, a computing package for automata and finite semigroups. J. Symb. Comput. 12 (1991) 197-220. | Zbl | MR

[11] R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1-15. | Zbl | MR

[12] D. Cowan, Inverse monoids of dot-depth $2$. Int. J. Algebra and Comput. 3 (1993) 411-424. | Zbl | MR

[13] S. Eilenberg. Automata, languages and machines, Vol. B. Academic Press, New York (1976). | Zbl | MR

[14] V. Froidure and J.-E. Pin, Algorithms for computing finite semigroups, in Foundations of Computational Mathematics, edited by F. Cucker and M. Shub. Springer, Berlin (1997) 112-126. | Zbl | MR

[15] C. Glaßer and H. Schmitz, 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. | Zbl | MR

[16] C. Glaßer and H. Schmitz, 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. | Zbl | MR

[17] C. Glaßer and H. Schmitz, Concatenation Hierarchies and Forbidden Patterns, Technical Report No. 256. University of Wuerzburg (2000).

[18] C. Glaßer and H. Schmitz, Level $5/2$ of the Straubing-Thérien hierarchy for two-letter alphabets (to appear). | Zbl

[19] T. Hall and P. Weil, On radical congruence systems. Semigroup Forum 59 (1999) 56-73. | Zbl | MR

[20] K. Henckell, S.W. Margolis, J.-E. Pin and J. Rhodes, Ash's Type II Theorem, Profinite Topology and Malcev Products. Int. J. Algebra and Comput. 1 (1991) 411-436. | Zbl

[21] R. Knast, A semigroup characterization of dot-depth one languages. RAIRO: Theoret. Informatics Appl. 17 (1983) 321-330. | Zbl | MR | Numdam

[22] R. Knast, Some theorems on graph congruences. RAIRO: Theoret. Informatics Appl. 17 (1983) 331-342. | MR | Numdam

[23] R. Mcnaughton and S. Pappert, Counter-free Automata. MIT Press (1971). | Zbl | MR

[24] S.W. Margolis and J.-E. Pin, Product of group languages, in FCT Conference. Springer, Lecture Notes in Comput. Sci. 199 (1985) 285-299. | Zbl | MR

[25] S.W. Margolis and B. Steinberg, Power semigroups and polynomial closure, in Proc. of the Third International Colloquium on Words, Languages and Combinatorics (to appear). | MR

[26] J.-E. Pin, Hiérarchies de concaténation. RAIRO: Theoret. Informatics Appl. 18 (1984) 23-46. | Zbl | MR | Numdam

[27] J.-E. Pin, Variétés de langages formels. Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986). | Zbl | MR

[28] J.-E. Pin, A property of the Schützenberger product. Semigroup Forum 35 (1987) 53-62. | Zbl | MR

[29] J.-E. Pin, A variety theorem without complementation. Izvestiya VUZ Matematika 39 (1995) 80-90. English version, Russian Mathem. (Iz. VUZ) 39 (1995) 74-83. | Zbl | MR

[30] J.-E. Pin, Syntactic semigroups, Chap. 10, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa. Springer (1997). | MR

[31] J.-E. Pin, Bridges for concatenation hierarchies, in 25th ICALP. Springer, Berlin, Lecture Notes in Comput. Sci. 1443 (1998) 431-442. | Zbl | MR

[32] J.-E. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. (to appear). | Zbl | MR

[33] J.-E. Pin and H. Straubing, Monoids of upper triangular matrices. Colloq. Math. Soc. János Bolyai 39 (1981) 259-272. | Zbl | MR

[34] J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis 35 (1996) 577-595. | Zbl | MR

[35] J.-E. Pin&P. Weil, Profinite semigroups, Mal'cev products and identities. J. Algebra 182 (1996) 604-626. | Zbl

[36] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 1-39. | Zbl | MR

[37] J.-E. Pin and P. Weil, The wreath product principle for ordered semigroups. Comm. in Algebra (to appear). | Zbl | MR

[38] M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control 8 (1965) 190-194. | Zbl | MR

[39] V. Selivanov, 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. | Zbl | MR

[40] I. Simon, Piecewise testable events, in Proc. 2nd GI Conf. Springer, Lecture Notes in Comput. Sci. 33 (1975) 214-222. | Zbl | MR

[41] B. Steinberg, Polynomial closure and topology. Int. J. Algebra and Comput. 10 (2000) 603-624. | Zbl | MR

[42] H. Straubing, Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra 15 (1979) 319-327. | Zbl | MR

[43] H. Straubing, A generalization of the Schützenberger product of finite monoids. Theory Comput. Systems 13 (1981) 137-150. | Zbl | MR

[44] H. Straubing, Relational morphisms and operations on recognizable sets. RAIRO: Theoret. Informatics Appl. 15 (1981) 149-159. | Zbl | MR | Numdam

[45] H. Straubing, Finite semigroups varieties of the form $𝐕*𝔻$. J. Pure Appl. Algebra 36 (1985) 53-94. | Zbl | MR

[46] H. Straubing. Semigroups and languages of dot-depth two. Theoret. Comput. Sci. 58 (1988) 361-378. | Zbl | MR

[47] H. Straubing and P. Weil, On a conjecture concerning dot-depth two languages. Theoret. Comput. Sci. 104 (1992) 161-183. | Zbl | MR

[48] D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. | Zbl | MR

[49] W. Thomas, Classifying regular events in symbolic logic. J. Comput. Syst. Sci. 25 (1982) 360-375. | Zbl | MR

[50] W. Thomas, An application of the Ehrenfeucht-Fraïssé game in formal language theory. Bull. Soc. Math. France 16 (1984) 11-21. | Zbl | Numdam

[51] W. Thomas, 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. | Zbl | MR

[52] P. Trotter&P. Weil, The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Universalis 37 (1997) 491-526. | Zbl | MR

[53] P. Weil, Inverse monoids of dot-depth two. Theoret. Comput. Sci. 66 (1989) 233-245. | Zbl | MR

[54] P. Weil, Some results on the dot-depth hierarchy. Semigroup Forum 46 (1993) 352-370. | Zbl | MR