Le rôle des relations rudimentaires en théorie de la complexité
The role of rudimentary relations in complexity theory
Anglais
On étudie dans cet article les classes $R*$ et $XR$ des relations rudimentaires et faiblement rudimentaires qui se reposent sur la relation de la concaténation bornée. On obtient $RUD$ et $XRUD$, les classes correspondantes des langages, comme l'union d'une hiérarchie linéaire resp. polynomiale. Ces hiérarchies utilisent des quantificateurs alternants aux longueurs bornés ou également des machines alternantes de Turing avec alternance constante. Nous allons introduire une autre description utilisant des quantificateurs alternants pour des oracles. En plus on obtiendra une chaîne nouvelle des hiérarchies pour tous les niveaux exponentiels, dont l'union sera $ERUD$, l'analogue exponentiel de la classe $RUD$. Et on va montrer que $ERUD$ est la classe $E_3$ des langages élémentaires.