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
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.