One of the most fascinating problem in automata theory is
the so-called "dot-depth 2" problem. It admits several equivalent
formulations

- Combinatorial version. Is there an algorithm to decide whether agiven rational language is a booelan combination of languages of the form , where the 's are letters and the 's are subsets of the alphabet ?

- Algebraic version. Is there an algorithm to decide whether a given finite monoid divides, for some , a monoid of by upper-triangular boolean matrices ?

- Logical version. Is there an algorithm to decide whether a first order formula of Büchi's sequential calculus is equivalent (on finite words) with a boolean combination of -formulas ?

This problem is only a special case of the decidability problem for
the Straubing-Thérien hierarchy. In this lecture, we shall survey
some open problems (and a few partial results) on concatenation
hierarchies, and their connection with semigroups, logic and
combinatorics.

Sponsored in part by the FCT approved
projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with
the European Community Fund FEDER and by FCT through *Centro de Matemática
da Universidade do Porto.* Also sponsored in part by FCT, the
*Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III*, and by *Caixa Geral de Depósitos*.