Contributions a l'etude du non-determinisme restreint.

摘要

Dans ce travail nous etudions un certain nombre de classes de compexite qui ont une saveur "non-deterministe" et qui sont plus petites que la classe NP des langages reconnus en temps non-deterministe polynomial. Nos recherches sont issues du modele des programmes sur monoide de Barrington et Therien (11), qui montrent, grace a ce modele, l'existence d'un lien etroit entre les proprietes algebriques des semi-groupes et les sous-classes de NC;Ce type d'approche est generalisee par Bedard, Lemieux et McKenzie (14). Ceux-ci introduisent le "non-determinisme" en remplacant les semi-groupes par des algebres finies avec lois de composition interne non associatives, ou groupoides. Le modele de calcul ainsi obtenu est plus puissant, puisqu'il permet d'acceder a diverses classes de langages comprises entre NC;Cette etude montre l'importance d'un element absorbant dans les groupoides. Les quasi-groupes sont des exemples typiques de groupoides sans element absorbant (un quasi-groupe est un groupoide dont la table forme un carre latin). Dans la deuxieme partie de ce travail, nous decrivons une technique generale pour etudier les problemes de mot sur un quasi-groupe. Cette technique permet de montrer que de tels problemes sont reguliers.;Grace aux idees developpees dans le contexte des "langages de feuilles" (20, 43, 47), nous definissons pour finir, une autre generalisation "non-deterministe" du modele des programmes de branchement sur monoide. Nous adaptons et generalisons certaines techniques utilisees sur des modeles plus puissants (43, 47). Nous montrons comment ce modele peut definir de bons candidats pour obtenir des sous-classes de NC;Comme sous-produit de nos travaux montrons commet les techniques classiques s'appliquent pour montrer deux nouvelles bornes inferieures. Tout d'abord nous montrons que la fonction ET ne peut pas etre calculee par un circuit de taille polynomiale et de profondeur 2 constitue de portes MOD