A conjecture on the concatenation product

Jean-Eric Pin; Pascal Weil

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 35.6 (2010): 597-618. <http://eudml.org/doc/92687>.

@article{Pin2010,
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},
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},
month = {3},
number = {6},
pages = {597-618},
publisher = {EDP Sciences},
title = {A conjecture on the concatenation product},
url = {http://eudml.org/doc/92687},
volume = {35},
year = {2010},
}

TY - JOUR
AU - Pin, Jean-Eric
AU - Weil, Pascal
TI - A conjecture on the concatenation product
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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/92687
ER -

References

top
  1. J. Almeida, Finite semigroups and universal algebra. Series in Algebra, Vol. 3. WorldScientific, Singapore (1994).  Zbl0844.20039
  2. J. Almeida and P. Weil, Free profinite -trivial monoids. Int. J. Algebra Comput.7 (1997) 625-671.  Zbl0892.20035
  3. M. Arfi, Polynomial operations and rational languages, in 4th STACS. Springer, Lecture Notes in Comput. Sci.247 (1987) 198-206.  
  4. M. Arfi, Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci.91 (1991) 71-84.  Zbl0751.68031
  5. F. Blanchet-Sadri, On dot-depth two. RAIRO: Theoret. Informatics Appl.24 (1990) 521-530.  Zbl0718.68046
  6. F. Blanchet-Sadri, On a complete set of generators for dot-depth two. Discrete Appl. Math.50 (1994) 1-25.  Zbl0793.68087
  7. J.A. Brzozowski, Hierarchies of aperiodic languages. RAIRO Theoret. Informatics. Appl.10 (1976) 33-49.  
  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.68074
  9. J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math.6 (1960) 66-92.  Zbl0103.24705
  10. J.M. Champarnaud and G. Hansel, AUTOMATE, a computing package for automata and finite semigroups. J. Symb. Comput.12 (1991) 197-220.  Zbl0804.68096
  11. R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci.5 (1971) 1-15.  Zbl0217.29602
  12. D. Cowan, Inverse monoids of dot-depth 2. Int. J. Algebra and Comput.3 (1993) 411-424.  Zbl0816.20064
  13. S. Eilenberg. Automata, languages and machines, Vol. B. Academic Press, New York (1976).  Zbl0359.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.  Zbl0876.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.  Zbl0962.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.  Zbl1044.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).  Zbl1073.68046
  19. T. Hall and P. Weil, On radical congruence systems. Semigroup Forum59 (1999) 56-73.  Zbl0946.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.  Zbl0791.20079
  21. R. Knast, A semigroup characterization of dot-depth one languages. RAIRO: Theoret. Informatics Appl.17 (1983) 321-330.  Zbl0522.68063
  22. R. Knast, Some theorems on graph congruences. RAIRO: Theoret. Informatics Appl.17 (1983) 331-342.  
  23. R. McNaughton and S. Pappert, Counter-free Automata. MIT Press (1971).  
  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.  
  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).  Zbl1291.20056
  26. J.-E. Pin, Hiérarchies de concaténation. RAIRO: Theoret. Informatics Appl.18 (1984) 23-46.  
  27. J.-E. Pin, Variétés de langages formels. Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986).  
  28. J.-E. Pin, A property of the Schützenberger product. Semigroup Forum35 (1987) 53-62.  Zbl0618.20040
  29. J.-E. Pin, A variety theorem without complementation. Izvestiya VUZ Matematika39 (1995) 80-90.  
  30. J.-E. Pin, Syntactic semigroups, Chap. 10, in Handbook of formal languages, edited byG. Rozenberg and A. Salomaa. Springer (1997).  
  31. J.-E. Pin, Bridges for concatenation hierarchies, in 25th ICALP. Springer, Berlin, Lecture Notes in Comput. Sci.1443 (1998) 431-442.  Zbl0909.68113
  32. J.-E. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. (to appear).  Zbl1064.68057
  33. J.-E. Pin and H. Straubing, Monoids of upper triangular matrices. Colloq. Math. Soc. János Bolyai39 (1981) 259-272.  Zbl0635.20028
  34. J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis35 (1996) 577-595.  Zbl0864.03024
  35. J.-E. Pinand P. Weil, Profinite semigroups, Mal'cev products and identities. J. Algebra182 (1996) 604-626.  Zbl0857.20040
  36. J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems30 (1997) 1-39.  Zbl0872.68119
  37. J.-E. Pin and P. Weil, The wreath product principle for ordered semigroups. Comm. in Algebra (to appear).  Zbl1017.06008
  38. M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control8 (1965) 190-194.  Zbl0131.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.  Zbl0976.03042
  40. I. Simon, Piecewise testable events, in Proc. 2nd GI Conf. Springer, Lecture Notes in Comput. Sci.33 (1975) 214-222.  Zbl0316.68034
  41. B. Steinberg, Polynomial closure and topology. Int. J. Algebra and Comput.10 (2000) 603-624.  Zbl1010.20045
  42. H. Straubing, Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra15 (1979) 319-327.  Zbl0407.20056
  43. H. Straubing, A generalization of the Schützenberger product of finite monoids. Theory Comput. Systems13 (1981) 137-150.  Zbl0456.20048
  44. H. Straubing, Relational morphisms and operations on recognizable sets. RAIRO: Theoret. Informatics Appl.15 (1981) 149-159.  Zbl0463.20049
  45. H. Straubing, Finite semigroups varieties of the form V*D. J. Pure Appl. Algebra36 (1985) 53-94.  Zbl0561.20042
  46. H. Straubing. Semigroups and languages of dot-depth two. Theoret. Comput. Sci.58 (1988) 361-378.  Zbl0655.18004
  47. H. Straubing and P. Weil, On a conjecture concerning dot-depth two languages. Theoret. Comput. Sci.104 (1992) 161-183.  Zbl0762.68037
  48. D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.  Zbl0471.20055
  49. W. Thomas, Classifying regular events in symbolic logic. J. Comput. Syst. Sci.25 (1982) 360-375.  Zbl0503.68055
  50. W. Thomas, An application of the Ehrenfeucht-Fraïssé game in formal language theory. Bull. Soc. Math. France16 (1984) 11-21.  Zbl0558.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.  
  52. P. Trotterand P. Weil, The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Universalis37 (1997) 491-526.  Zbl0906.20036
  53. P. Weil, Inverse monoids of dot-depth two. Theoret. Comput. Sci.66 (1989) 233-245.  Zbl0678.68075
  54. P. Weil, Some results on the dot-depth hierarchy. Semigroup Forum46 (1993) 352-370.  Zbl0778.20025

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.