Inverse monoids and the dot-depth hierarchy

Finite automata and rational languages are fundamental concepts in theoretical computer science and they have been extensively studied since the 1950\u27s. The seminal result was Kleene\u27s famous theorem. It rapidly appeared, especially in Schutzenberger\u27s and Rhodes\u27 work, that this study was naturally linked with the algebraic study of finite semigroups and monoids. More precisely, to each rational language, one can associate a finite semigroup whose algebraic structure reflects many combinatorial properties of the language. It is on this basis that most of the research in this field has developed since the 1960\u27s, especially since Eilenberg gave a formal framework for this natural link. The central consideration of this dissertation is a famous problem of language theory, namely the decidability of the dot-depth hierarchy. This hierarchy, introduced by Brzozowski, arises naturally as a measure of complexity for a well-known class of rational languages, the star-free languages. The first part of this work consists of a survey of the results known to date concerning the hierarchy. It is followed by a few results, some old, some new, about upper and lower bounds to the dot-depth of a given language. Next we consider the same problem from the point of view of semigroup theory, and restrict it to the case of inverse semigroups and monoids. A large class of inverse semigroups is described by finite subgraphs of the Cayley graph of the free group. We present general techniques to determine the structure of these semigroups from the geometrical features of these graphs. This allows us to give a new result of partial decidability for the second level of the dot-depth hierarchy. We show that it is decidable for inverse monoids with up to three inverse generators