Abstract FR:

Le travail presente dans cette these part d'un double constat : d'une part le theoreme de rabin affirme que tout langage unique solution d'une formule de logique monadique du second ordre du successeur de rabin est rationnel, de facon constructive mais avec une complexite non elementaire : d'autre part, l'algorithme de ramadge-wonham developpe en theorie des systemes a evenements discrets donne un cas particulier de formule pour laquelle ou sait obtenir un automate equivalent en temps polynomial, lineaire ou quadratique selon les donnees. On part ici d'un probleme formellement inspire de l'automatique pour lequel on donne une solution de complexite raisonnable, c'est-a-dire au plus simplement exponentielle par rapport a l'un des parametres de depart. Il s'agit plus precisement de calculer la borne superieure de l'ensemble des langages x tels que ax x b, sous la contrainte x k. Ou a, b et k sont des parametres rationnels fixes. A cette fin, on a developpe un nouvel outil qui associe le systeme de transition sous-jacent a un automate classique et une formule booleenne positive qui donne les conditions d'acceptation. Cet outil permet de simuler les operations d'union et d'intersection sans les effectuer, d'ou un gain de place et de temps important, ce qui permet de donner un algorithme efficace pour resoudre le probleme pose. La these aborde ensuite une generalisation de cet outil et de son application aux series formelles a coefficients dans certains semi-anneaux idempotents complets. Cette adaptation aux series nous fait sortir du domaine du reconnaissable, on introduit alors une nouvelle notion de regularite sur les series, la pseudo-reconnaissabilite, et on montre que sous certaines conditions pour les parametres, la solution est pseudo-reconnaissable. Enfin, on analyse la puissance de ces nouvelles representations de series en les comparant a un type de representations introduit par j. -e. Pin et j. Sakarovitch en 1985 et en construisant une generalisation commune aux deux.