A conjecture on the concatenation product

Pin, Jean-Eric ; Weil, Pascal

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 597-618 / Harvested from Numdam

Résumé

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.

Détail

Publié le : 2001-01-01

MR 1922298 | Zbl 1011.20054

DOI : https://doi.org/10.1051/ita:2001134
Classification:  20M07,  68Q45,  20M35

Bibliographie

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

[2] J. Almeida and P. Weil, Free profinite ${\mathcal {R}}$-trivial monoids. Int. J. Algebra Comput. 7 (1997) 625-671. | MR 1470356 | Zbl 0892.20035

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

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

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

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

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

[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. | MR 471451 | Zbl 0368.68074

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

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

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

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

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

[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. | MR 1661975 | Zbl 0876.20034

[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. | MR 1781762 | Zbl 0962.68093

[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. | MR 1850121 | Zbl 1044.68091

[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 1073.68046

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

[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 0791.20079

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

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

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

[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. | MR 821246 | Zbl 0602.68063

[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 2028884

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

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

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

[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. | MR 1391325 | Zbl 0852.20059

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

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

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

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

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

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

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

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

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

[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. | MR 1892340 | Zbl 0976.03042

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

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

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

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

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

[45] H. Straubing, Finite semigroups varieties of the form $\mathbf {V}*\mathbb {D}$. J. Pure Appl. Algebra 36 (1985) 53-94. | MR 782639 | Zbl 0561.20042

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

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

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

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

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

[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. | MR 907535 | Zbl 0643.68073

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

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

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