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).  
  2. J. Almeida and P. Weil, Free profinite ℛ -trivial monoids. Int. J. Algebra Comput.7 (1997) 625-671.  
  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.  
  5. F. Blanchet-Sadri, On dot-depth two. RAIRO: Theoret. Informatics Appl.24 (1990) 521-530.  
  6. F. Blanchet-Sadri, On a complete set of generators for dot-depth two. Discrete Appl. Math.50 (1994) 1-25.  
  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.  
  9. J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math.6 (1960) 66-92.  
  10. J.M. Champarnaud and G. Hansel, AUTOMATE, a computing package for automata and finite semigroups. J. Symb. Comput.12 (1991) 197-220.  
  11. R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci.5 (1971) 1-15.  
  12. D. Cowan, Inverse monoids of dot-depth 2. Int. J. Algebra and Comput.3 (1993) 411-424.  
  13. S. Eilenberg. Automata, languages and machines, Vol. B. Academic Press, New York (1976).  
  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.  
  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.  
  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.  
  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).  
  19. T. Hall and P. Weil, On radical congruence systems. Semigroup Forum59 (1999) 56-73.  
  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.  
  21. R. Knast, A semigroup characterization of dot-depth one languages. RAIRO: Theoret. Informatics Appl.17 (1983) 321-330.  
  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).  
  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.  
  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.  
  32. J.-E. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. (to appear).  
  33. J.-E. Pin and H. Straubing, Monoids of upper triangular matrices. Colloq. Math. Soc. János Bolyai39 (1981) 259-272.  
  34. J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis35 (1996) 577-595.  
  35. J.-E. Pinand P. Weil, Profinite semigroups, Mal'cev products and identities. J. Algebra182 (1996) 604-626.  
  36. J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems30 (1997) 1-39.  
  37. J.-E. Pin and P. Weil, The wreath product principle for ordered semigroups. Comm. in Algebra (to appear).  
  38. M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control8 (1965) 190-194.  
  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.  
  40. I. Simon, Piecewise testable events, in Proc. 2nd GI Conf. Springer, Lecture Notes in Comput. Sci.33 (1975) 214-222.  
  41. B. Steinberg, Polynomial closure and topology. Int. J. Algebra and Comput.10 (2000) 603-624.  
  42. H. Straubing, Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra15 (1979) 319-327.  
  43. H. Straubing, A generalization of the Schützenberger product of finite monoids. Theory Comput. Systems13 (1981) 137-150.  
  44. H. Straubing, Relational morphisms and operations on recognizable sets. RAIRO: Theoret. Informatics Appl.15 (1981) 149-159.  
  45. H. Straubing, Finite semigroups varieties of the form V*D. J. Pure Appl. Algebra36 (1985) 53-94.  
  46. H. Straubing. Semigroups and languages of dot-depth two. Theoret. Comput. Sci.58 (1988) 361-378.  
  47. H. Straubing and P. Weil, On a conjecture concerning dot-depth two languages. Theoret. Comput. Sci.104 (1992) 161-183.  
  48. D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.  
  49. W. Thomas, Classifying regular events in symbolic logic. J. Comput. Syst. Sci.25 (1982) 360-375.  
  50. W. Thomas, An application of the Ehrenfeucht-Fraïssé game in formal language theory. Bull. Soc. Math. France16 (1984) 11-21.  
  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.  
  53. P. Weil, Inverse monoids of dot-depth two. Theoret. Comput. Sci.66 (1989) 233-245.  
  54. P. Weil, Some results on the dot-depth hierarchy. Semigroup Forum46 (1993) 352-370.  

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.