SMF

Le rôle des relations rudimentaires en théorie de la complexité

The role of rudimentary relations in complexity theory

H. VOLGER
Le rôle des relations rudimentaires en théorie de la complexité
  • Année : 1984
  • Tome : 16
  • Format : Électronique
  • Langue de l'ouvrage :
    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.

We shall study the classes $R$ resp. $XR$ of rudimentary resp. extended rudimentary relations which are based on the relation of bounded concatenation. The associated classes $RUD$ resp. $XRUD$ of languages are the union of a linear - resp. polynomial time hierarchy. It can be described either by means of alternating length bounded quantifiers or by means of Turing machines with constant alternation. We shall introduce another description based on alternating quantifiers for oracle sets. Extending these results we obtain a chain of hierarchies for the iterated exponential time levels, whose union is the $ERUD$, the exponential analogue of $RUD$. Moreover, it will be shown that $ERUD$ coincides with the class of elementary recursive languages.



Des problèmes avec le téléchargement?Des problèmes avec le téléchargement?
Informez-nous de tout problème que vous avez...