Les langages réguliers sont des langages qui ont été largement étudiés, notamment du point de vue de leurs propriétés de clôture ensembliste : l'ensemble des langages réguliers (pour un alphabet donné) forme une algèbre de Boole close par concaténation et étoile de Kleene. Ces propriétés ne se généralisent pas toutes à l ensemble des langages algébriques qui est un sur-ensemble de l'ensemble des langages réguliers. Notamment les langages algébriques ne sont pas clos par intersection. Pour engendrer ces langages, nous utilisons les grammaires déterministes de graphes. Une grammaire de graphes est un système fini de récriture d'hypergraphes finis. Par récriture itérée à partir d'un non-terminal, la grammaire engendre un graphe régulier dont les traces forment un langage algébrique. En définissant une relation de synchronisation entre ces grammaires, on montre que l'on peut définir des sous-ensembles stricts de langages algébriques non-ambigus qui forment des algèbres de Boole effectives contenant les langages réguliers. Nous donnons également des conditions suffisantes pour que ces algèbres booléennes soient closes par concaténation et étoile de Kleene.

Le problème de séparation pour une classe de langages S est le suivant : étant donnés deux langages L1 et L2, existe-t-il un langage appartenant à S qui contient L1, en étant disjoint de L2 ? Si les langages à séparer sont des langages réguliers, le problème de séparation pour la classe S est plus général que le problème de l'appartenance à cette classe, et nous fournit des informations plus détaillées sur la classe. Ce problème de séparation apparaît dans un contexte algébrique sous la forme des parties ponctuelles, et dans un contexte profini sous la forme d'un problème de séparation topologique. Pour quelques classes de langages spécifiques, ce problème a été étudié en utilisant des méthodes profondes de la théorie des semigroupes profinis.Dans cette thèse, on s'intéresse, dans un premier temps, à la décidabilité de ce problème pour plusieurs sous-classes des langages réguliers. Dans un second temps, on s'intéresse à obtenir un langage séparateur, s'il existe, ainsi qu'à la complexité de ces problèmes.Nous établissons une approche générique pour prouver que le problème de séparation est décidable pour une classe de langages donnée. En utilisant cette approche, nous obtenons la décidabilité du problème de séparation pour les langages testables par morceaux, les langages non-ambigus, les langages localement testables, et les langages localement testables à seuil. Ces classes correspondent à des fragments de la logique du premier ordre, et sont parmi lesclasses de langages réguliers les plus étudiées. De plus, cette approche donne une description d'un langage séparateur, pourvu qu'il existe. / The separation problem, for a class S of languages, is the following: given two input languages, does there exist a language in S that contains the first language and that is disjoint from the second langage ?For regular input languages, the separation problem for a class S subsumes the classical membership problem for this class, and provides more detailed information about the class. This separation problem first emerged in an algebraic context in the form of pointlike sets, and in a profinite context as a topological separation problem. These problems have been studied for specific classes of languages, using involved techniques from the theory of profinite semigroups.In this thesis, we are not only interested in showing the decidability of the separation problem for several subclasses of the regular languages, but also in constructing a separating language, if it exists, and in the complexity of these problems.We provide a generic approach, based on combinatorial arguments, to proving the decidability of this problem for a given class. Using this approach, we prove that the separation problem is decidable for the classes of piecewise testable languages, unambiguous languages, and locally (threshold) testable languages. These classes are defined by different fragments of first-order logic, and are among the most studied classes of regular languages. Furthermore, our approach yields a description of a separating language, in case it exists.