Open problems on concatenation hierarchies








J.-E. Pin
CNRS, University of Paris VII, LIAFA, France






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 $A^*_0a_1A^*_1 \ldots a_nA^*_n$, where the $a_i$'s are letters and the $A_i$'s are subsets of the alphabet ?

- Algebraic version. Is there an algorithm to decide whether a given finite monoid divides, for some $n$, a monoid of $n$ by $n$ 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 $\Sigma_2$-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.

 

 Return to the top of the page