Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T17:06:00.008Z Has data issue: false hasContentIssue false
  • English
  • Français

A conjecture on the concatenation product

Published online by Cambridge University Press:  15 July 2002

Jean-Eric Pin  and
Pascal Weil
Jean-Eric Pin
Affiliation:
LIAFA, Université Paris VII et CNRS, Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; ([email protected])
Pascal Weil
Affiliation:
LaBRI, Université Bordeaux I et CNRS, 351 cours de la Libération, 33405 Talence Cedex, France; ([email protected])
Get access

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.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 6: A tribute to Aldo de Luca , November 2001 , pp. 597 - 618
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Almeida, Finite semigroups and universal algebra. Series in Algebra, Vol. 3. WorldScientific, Singapore (1994).
Almeida, J. and Weil, P., Free profinite ${\cal R}$ -trivial monoids. Int. J. Algebra Comput. 7 (1997) 625-671. CrossRef
Arfi, M., Polynomial operations and rational languages, in 4th STACS. Springer, Lecture Notes in Comput. Sci. 247 (1987) 198-206. CrossRef
Arfi, M., Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91 (1991) 71-84. CrossRef
Blanchet-Sadri, F., On dot-depth two. RAIRO: Theoret. Informatics Appl. 24 (1990) 521-530.
Blanchet-Sadri, F., On a complete set of generators for dot-depth two. Discrete Appl. Math. 50 (1994) 1-25. CrossRef
Brzozowski, J.A., Hierarchies of aperiodic languages. RAIRO Theoret. Informatics. Appl. 10 (1976) 33-49.
Brzozowski, J.A. and Knast, R., The dot-depth hierarchy of star-free languages is infinite. J. Comput. System Sci. 16 (1978) 37-55. CrossRef
Büchi, J.R., Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math. 6 (1960) 66-92. CrossRef
Champarnaud, J.M. and Hansel, G., AUTOMATE, a computing package for automata and finite semigroups. J. Symb. Comput. 12 (1991) 197-220. CrossRef
Cohen, R.S. and Brzozowski, J.A., Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1-15. CrossRef
Cowan, D., Inverse monoids of dot-depth 2. Int. J. Algebra and Comput. 3 (1993) 411-424. CrossRef
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.
Glaßer, C. and Schmitz, H., 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. CrossRef
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).
Hall, T. and Weil, P., On radical congruence systems. Semigroup Forum 59 (1999) 56-73. CrossRef
Henckell, K., Margolis, S.W., Pin, J.-E. and Rhodes, J., Ash's Type II Theorem, Profinite Topology and Malcev Products. Int. J. Algebra and Comput. 1 (1991) 411-436. CrossRef
Knast, R., A semigroup characterization of dot-depth one languages. RAIRO: Theoret. Informatics Appl. 17 (1983) 321-330.
Knast, R., 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).
Pin, J.-E., 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).
Pin, J.-E., A property of the Schützenberger product. Semigroup Forum 35 (1987) 53-62. CrossRef
Pin, J.-E., A variety theorem without complementation. Izvestiya VUZ Matematika 39 (1995) 80-90.
J.-E. Pin, Syntactic semigroups, Chap. 10, in Handbook of formal languages, edited byG. Rozenberg and A. Salomaa. Springer (1997).
Pin, J.-E., Bridges for concatenation hierarchies, in 25th ICALP. Springer, Berlin, Lecture Notes in Comput. Sci. 1443 (1998) 431-442. CrossRef
J.-E. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. (to appear).
Pin, J.-E. and Straubing, H., Monoids of upper triangular matrices. Colloq. Math. Soc. János Bolyai 39 (1981) 259-272.
Pin, J.-E. and Weil, P., Reiterman, A theorem for pseudovarieties of finite first-order structures. Algebra Universalis 35 (1996) 577-595. CrossRef
Pinand, J.-E. Weil, P., Profinite semigroups, Mal'cev products and identities. J. Algebra 182 (1996) 604-626.
Pin, J.-E. and Weil, P., Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 1-39. CrossRef
J.-E. Pin and P. Weil, The wreath product principle for ordered semigroups. Comm. in Algebra (to appear).
Schützenberger, M.P., On finite monoids having only trivial subgroups. Inform. and Control 8 (1965) 190-194. CrossRef
Selivanov, V., 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. CrossRef
Simon, I., Piecewise testable events, in Proc. 2nd GI Conf. Springer, Lecture Notes in Comput. Sci. 33 (1975) 214-222. CrossRef
Steinberg, B., Polynomial closure and topology. Int. J. Algebra and Comput. 10 (2000) 603-624. CrossRef
Straubing, H., Aperiodic homomorphisms and the concatenation product of recognizable sets. J. Pure Appl. Algebra 15 (1979) 319-327. CrossRef
Straubing, H., A generalization of the Schützenberger product of finite monoids. Theory Comput. Systems 13 (1981) 137-150. CrossRef
Straubing, H., Relational morphisms and operations on recognizable sets. RAIRO: Theoret. Informatics Appl. 15 (1981) 149-159.
Straubing, H., Finite semigroups varieties of the form V*D. J. Pure Appl. Algebra 36 (1985) 53-94. CrossRef
H. Straubing. Semigroups and languages of dot-depth two. Theoret. Comput. Sci. 58 (1988) 361-378.
Straubing, H. and Weil, P., On a conjecture concerning dot-depth two languages. Theoret. Comput. Sci. 104 (1992) 161-183. CrossRef
Thérien, D., Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. CrossRef
Thomas, W., Classifying regular events in symbolic logic. J. Comput. Syst. Sci. 25 (1982) 360-375. CrossRef
Thomas, W., An application of the Ehrenfeucht-Fraïssé game in formal language theory. Bull. Soc. Math. France 16 (1984) 11-21.
Thomas, W., 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. CrossRef
Trotterand, P. Weil, P., The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Universalis 37 (1997) 491-526. CrossRef
Weil, P., Inverse monoids of dot-depth two. Theoret. Comput. Sci. 66 (1989) 233-245. CrossRef
Weil, P., Some results on the dot-depth hierarchy. Semigroup Forum 46 (1993) 352-370. CrossRef