A conjecture on the concatenation product

Jean-Eric Pin; Pascal Weil

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • Volume: 35, Issue: 6, page 597-618
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Pin, Jean-Eric, and Weil, Pascal. "A conjecture on the concatenation product." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.6 (2001): 597-618. <http://eudml.org/doc/244944>.

@article{Pin2001,
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.},
author = {Pin, Jean-Eric, Weil, Pascal},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {rational languages; star-free languages; concatenation products; concatenation hierarchies; dot-depth hierarchies; pseudovarieties of semigroups; Mal'cev products; varieties of languages; semidirect products},
language = {eng},
number = {6},
pages = {597-618},
publisher = {EDP-Sciences},
title = {A conjecture on the concatenation product},
url = {http://eudml.org/doc/244944},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 6
SP - 597
EP - 618
AB - 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.
LA - eng
KW - rational languages; star-free languages; concatenation products; concatenation hierarchies; dot-depth hierarchies; pseudovarieties of semigroups; Mal'cev products; varieties of languages; semidirect products
UR - http://eudml.org/doc/244944
ER -

References

top
  1. [1] J. Almeida, Finite semigroups and universal algebra. Series in Algebra, Vol. 3. World Scientific, Singapore (1994). Zbl0844.20039MR1331143
  2. [2] J. Almeida and P. Weil, Free profinite ℛ -trivial monoids. Int. J. Algebra Comput. 7 (1997) 625-671. Zbl0892.20035MR1470356
  3. [3] M. Arfi, Polynomial operations and rational languages, in 4th STACS. Springer, Lecture Notes in Comput. Sci. 247 (1987) 198-206. Zbl0635.68078MR900454
  4. [4] M. Arfi, Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91 (1991) 71-84. Zbl0751.68031MR1142558
  5. [5] F. Blanchet–Sadri, On dot-depth two. RAIRO: Theoret. Informatics Appl. 24 (1990) 521-530. Zbl0718.68046
  6. [6] F. Blanchet–Sadri, On a complete set of generators for dot-depth two. Discrete Appl. Math. 50 (1994) 1-25. Zbl0793.68087
  7. [7] J.A. Brzozowski, Hierarchies of aperiodic languages. RAIRO Theoret. Informatics. Appl. 10 (1976) 33-49. MR428813
  8. [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. Zbl0368.68074MR471451
  9. [9] J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math. 6 (1960) 66-92. Zbl0103.24705MR125010
  10. [10] J.M. Champarnaud and G. Hansel, AUTOMATE, a computing package for automata and finite semigroups. J. Symb. Comput. 12 (1991) 197-220. Zbl0804.68096MR1125939
  11. [11] R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1-15. Zbl0217.29602MR309676
  12. [12] D. Cowan, Inverse monoids of dot-depth 2 . Int. J. Algebra and Comput. 3 (1993) 411-424. Zbl0816.20064MR1250245
  13. [13] S. Eilenberg. Automata, languages and machines, Vol. B. Academic Press, New York (1976). Zbl0359.94067MR530383
  14. [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. Zbl0876.20034MR1661975
  15. [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. Zbl0962.68093MR1781762
  16. [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. Zbl1044.68091MR1850121
  17. [17] C. Glaßer and H. Schmitz, Concatenation Hierarchies and Forbidden Patterns, Technical Report No. 256. University of Wuerzburg (2000). 
  18. [18] C. Glaßer and H. Schmitz, Level 5 / 2 of the Straubing–Thérien hierarchy for two-letter alphabets (to appear). Zbl1073.68046
  19. [19] T. Hall and P. Weil, On radical congruence systems. Semigroup Forum 59 (1999) 56-73. Zbl0946.20033MR1847942
  20. [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. Zbl0791.20079
  21. [21] R. Knast, A semigroup characterization of dot-depth one languages. RAIRO: Theoret. Informatics Appl. 17 (1983) 321-330. Zbl0522.68063MR743892
  22. [22] R. Knast, Some theorems on graph congruences. RAIRO: Theoret. Informatics Appl. 17 (1983) 331-342. MR743893
  23. [23] R. McNaughton and S. Pappert, Counter-free Automata. MIT Press (1971). Zbl0232.94024MR371538
  24. [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. Zbl0602.68063MR821246
  25. [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). MR2028884
  26. [26] J.-E. Pin, Hiérarchies de concaténation. RAIRO: Theoret. Informatics Appl. 18 (1984) 23-46. Zbl0559.68062MR750449
  27. [27] J.-E. Pin, Variétés de langages formels. Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986). Zbl0636.68093MR752695
  28. [28] J.-E. Pin, A property of the Schützenberger product. Semigroup Forum 35 (1987) 53-62. Zbl0618.20040MR880350
  29. [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. Zbl0852.20059MR1391325
  30. [30] J.-E. Pin, Syntactic semigroups, Chap. 10, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa. Springer (1997). MR1470002
  31. [31] J.-E. Pin, Bridges for concatenation hierarchies, in 25th ICALP. Springer, Berlin, Lecture Notes in Comput. Sci. 1443 (1998) 431-442. Zbl0909.68113MR1683494
  32. [32] J.-E. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. (to appear). Zbl1064.68057MR1964641
  33. [33] J.-E. Pin and H. Straubing, Monoids of upper triangular matrices. Colloq. Math. Soc. János Bolyai 39 (1981) 259-272. Zbl0635.20028MR873155
  34. [34] J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis 35 (1996) 577-595. Zbl0864.03024MR1392285
  35. [35] J.-E. Pin& P. Weil, Profinite semigroups, Mal’cev products and identities. J. Algebra 182 (1996) 604-626. Zbl0857.20040
  36. [36] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 1-39. Zbl0872.68119MR1450862
  37. [37] J.-E. Pin and P. Weil, The wreath product principle for ordered semigroups. Comm. in Algebra (to appear). Zbl1017.06008MR1941918
  38. [38] M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control 8 (1965) 190-194. Zbl0131.02001MR176883
  39. [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. Zbl0976.03042MR1892340
  40. [40] I. Simon, Piecewise testable events, in Proc. 2nd GI Conf. Springer, Lecture Notes in Comput. Sci. 33 (1975) 214-222. Zbl0316.68034MR427498
  41. [41] B. Steinberg, Polynomial closure and topology. Int. J. Algebra and Comput. 10 (2000) 603-624. Zbl1010.20045MR1781850
  42. [42] H. Straubing, Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra 15 (1979) 319-327. Zbl0407.20056MR537504
  43. [43] H. Straubing, A generalization of the Schützenberger product of finite monoids. Theory Comput. Systems 13 (1981) 137-150. Zbl0456.20048MR594057
  44. [44] H. Straubing, Relational morphisms and operations on recognizable sets. RAIRO: Theoret. Informatics Appl. 15 (1981) 149-159. Zbl0463.20049MR618452
  45. [45] H. Straubing, Finite semigroups varieties of the form 𝐕 * 𝔻 . J. Pure Appl. Algebra 36 (1985) 53-94. Zbl0561.20042MR782639
  46. [46] H. Straubing. Semigroups and languages of dot-depth two. Theoret. Comput. Sci. 58 (1988) 361-378. Zbl0655.18004MR963270
  47. [47] H. Straubing and P. Weil, On a conjecture concerning dot-depth two languages. Theoret. Comput. Sci. 104 (1992) 161-183. Zbl0762.68037MR1186177
  48. [48] D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. Zbl0471.20055MR614416
  49. [49] W. Thomas, Classifying regular events in symbolic logic. J. Comput. Syst. Sci. 25 (1982) 360-375. Zbl0503.68055MR684265
  50. [50] W. Thomas, An application of the Ehrenfeucht–Fraïssé game in formal language theory. Bull. Soc. Math. France 16 (1984) 11-21. Zbl0558.68064
  51. [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. Zbl0643.68073MR907535
  52. [52] P. Trotter& P. Weil, The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Universalis 37 (1997) 491-526. Zbl0906.20036MR1465305
  53. [53] P. Weil, Inverse monoids of dot-depth two. Theoret. Comput. Sci. 66 (1989) 233-245. Zbl0678.68075MR1018561
  54. [54] P. Weil, Some results on the dot-depth hierarchy. Semigroup Forum 46 (1993) 352-370. Zbl0778.20025MR1206213

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.