# A conjecture on the concatenation product

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topPin, 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- J. Almeida, Finite semigroups and universal algebra. Series in Algebra, Vol. 3. WorldScientific, Singapore (1994).
- J. Almeida and P. Weil, Free profinite $\mathcal{R}$-trivial monoids. Int. J. Algebra Comput.7 (1997) 625-671.
- M. Arfi, Polynomial operations and rational languages, in 4th STACS. Springer, Lecture Notes in Comput. Sci.247 (1987) 198-206.
- M. Arfi, Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci.91 (1991) 71-84.
- F. Blanchet-Sadri, On dot-depth two. RAIRO: Theoret. Informatics Appl.24 (1990) 521-530.
- F. Blanchet-Sadri, On a complete set of generators for dot-depth two. Discrete Appl. Math.50 (1994) 1-25.
- J.A. Brzozowski, Hierarchies of aperiodic languages. RAIRO Theoret. Informatics. Appl.10 (1976) 33-49.
- J.A. Brzozowski and R. Knast, The dot-depth hierarchy of star-free languages is infinite. J. Comput. System Sci.16 (1978) 37-55.
- J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math.6 (1960) 66-92.
- J.M. Champarnaud and G. Hansel, AUTOMATE, a computing package for automata and finite semigroups. J. Symb. Comput.12 (1991) 197-220.
- R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci.5 (1971) 1-15.
- D. Cowan, Inverse monoids of dot-depth 2. Int. J. Algebra and Comput.3 (1993) 411-424.
- S. Eilenberg. Automata, languages and machines, Vol. B. Academic Press, New York (1976).
- 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.
- 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.
- 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.
- C. Glaßer and H. Schmitz, Concatenation Hierarchies and Forbidden Patterns, Technical Report No. 256. University of Wuerzburg (2000).
- C. Glaßer and H. Schmitz, Level 5/2 of the Straubing-Thérien hierarchy for two-letter alphabets (to appear).
- T. Hall and P. Weil, On radical congruence systems. Semigroup Forum59 (1999) 56-73.
- 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.
- R. Knast, A semigroup characterization of dot-depth one languages. RAIRO: Theoret. Informatics Appl.17 (1983) 321-330.
- R. Knast, Some theorems on graph congruences. RAIRO: Theoret. Informatics Appl.17 (1983) 331-342.
- R. McNaughton and S. Pappert, Counter-free Automata. MIT Press (1971).
- S.W. Margolis and J.-E. Pin, Product of group languages, in FCT Conference. Springer, Lecture Notes in Comput. Sci. 199 (1985) 285-299.
- 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).
- J.-E. Pin, Hiérarchies de concaténation. RAIRO: Theoret. Informatics Appl.18 (1984) 23-46.
- J.-E. Pin, Variétés de langages formels. Masson, Paris (1984); English translation: Varieties of formal languages. Plenum, New-York (1986).
- J.-E. Pin, A property of the Schützenberger product. Semigroup Forum35 (1987) 53-62.
- J.-E. Pin, A variety theorem without complementation. Izvestiya VUZ Matematika39 (1995) 80-90.
- J.-E. Pin, Syntactic semigroups, Chap. 10, in Handbook of formal languages, edited byG. Rozenberg and A. Salomaa. Springer (1997).
- J.-E. Pin, Bridges for concatenation hierarchies, in 25th ICALP. Springer, Berlin, Lecture Notes in Comput. Sci.1443 (1998) 431-442.
- J.-E. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. (to appear).
- J.-E. Pin and H. Straubing, Monoids of upper triangular matrices. Colloq. Math. Soc. János Bolyai39 (1981) 259-272.
- J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis35 (1996) 577-595.
- J.-E. Pinand P. Weil, Profinite semigroups, Mal'cev products and identities. J. Algebra182 (1996) 604-626.
- J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems30 (1997) 1-39.
- J.-E. Pin and P. Weil, The wreath product principle for ordered semigroups. Comm. in Algebra (to appear).
- M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control8 (1965) 190-194.
- 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.
- I. Simon, Piecewise testable events, in Proc. 2nd GI Conf. Springer, Lecture Notes in Comput. Sci.33 (1975) 214-222.
- B. Steinberg, Polynomial closure and topology. Int. J. Algebra and Comput.10 (2000) 603-624.
- H. Straubing, Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra15 (1979) 319-327.
- H. Straubing, A generalization of the Schützenberger product of finite monoids. Theory Comput. Systems13 (1981) 137-150.
- H. Straubing, Relational morphisms and operations on recognizable sets. RAIRO: Theoret. Informatics Appl.15 (1981) 149-159.
- H. Straubing, Finite semigroups varieties of the form V*D. J. Pure Appl. Algebra36 (1985) 53-94.
- H. Straubing. Semigroups and languages of dot-depth two. Theoret. Comput. Sci.58 (1988) 361-378.
- H. Straubing and P. Weil, On a conjecture concerning dot-depth two languages. Theoret. Comput. Sci.104 (1992) 161-183.
- D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.
- W. Thomas, Classifying regular events in symbolic logic. J. Comput. Syst. Sci.25 (1982) 360-375.
- W. Thomas, An application of the Ehrenfeucht-Fraïssé game in formal language theory. Bull. Soc. Math. France16 (1984) 11-21.
- 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.
- P. Trotterand P. Weil, The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Universalis37 (1997) 491-526.
- P. Weil, Inverse monoids of dot-depth two. Theoret. Comput. Sci.66 (1989) 233-245.
- P. Weil, Some results on the dot-depth hierarchy. Semigroup Forum46 (1993) 352-370.

## NotesEmbed ?

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