Abstract FR:

La fermeture polynomiale d'une classe de langages a ete definie par schutzenberger en 1975. Dans une premiere partie, nous etudions les fermetures polynomiales d'un point de vue combinatoire. Notre resultat principal dans cette direction montre en particulier que si une algebre de boole de langages reconnaissables est fermee par residuels, alors sa cloture polynomiale est stable par intersection finie. Ce resultat possede un corollaire interessant. Il nous permet d'affiner la hierarchie de concatenation proposee par straubing en y intercalant des niveaux polynomiaux. La seconde partie de notre expose est plus algebrique. On connait l'importance de la notion de semigroupe (ou monoide) syntactique dans l'etude des langages rationnels. Cette derniere ne suffit malheureusement pas a decrire de facon commode les fermetures polynomiales, puisque ces classes ne sont pas, en general, stables par complementation. Nous avons donc utilise le concept de monoide pointe, introduit par sakarovitch. Nous obtenons ainsi une caracterisation syntactique des clotures polynomiales, grace a un theoreme qui rappelle celui des varietes d'eilenberg. Enfin, la troisieme partie est relative aux problemes de decidabilite. Nous y demontrons en particulier que les deux premiers niveaux polynomiaux de la hierarchie decrite ci-dessus sont decidables