Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
Evaluation Dynamique et Optimisation des Structures CMOS et VLSI
No full textNuméro Spécial : CAO de VLSIInternational audienc
Optimalité d'une classe d'algorithmes d'ordonnancement pour la méthode de Gauss en parallèle
No full textInternational audienceno abstrac
Axiomatic approach to the theory of algorithms and relativized computability
No full textTraduction en anglais 2018International audienceIt is well known that many theorems in recursion theory can be "relativized". This means that they remain true if partial recursive functions are replaced by functions that are partial recursive relative to some fixed oracle set. Uspensky in [1] formulates three "axioms" called "axiom of computation records", "axiom of programs" and "arithmeticity axiom". Then, using these axioms (more precisely, two first ones) he proves basic results of the recursion theory. These two axioms are true also for the class of functions that are partial recursive relative to some fixed oracle set. Also this class is closed under substitution, primitive recursion and minimization (í µí¼-operator); these (intuitively obvious) closure properties are also used in the proofs. This observation made by Uspensky explains why many theorems of recursion theory can be relativized. It turns out that the reverse statement is also true: all relativizable results follow from the first two axioms and closure properties. Indeed, every class of partial functions that is closed under substitution, primitive recursion and minimization that satisfies the first two axioms is the class of functions that are partial recursive relative to some oracle set í µí°´. This is the main result of the present article. Let í µí°¾ be a class of partial functions with natural arguments and values. It may contain functions of different arity. Consider the following requirements for the class í µí°¾: 1. (Closure properties) The class í µí°¾ contains all partial recursive functions and is closed under substitution, primitive recursion and í µí¼-operator. 2. (Computation records) For every unary function ∈ í µí°¾ there exists a set í µí± of natural numbers and functions í µí»¼, í µí¼ ∈ í µí°¾ whose domains contain í µí± such that (a) The indicator function of the set í µí± that is equal to 1 on í µí± and is equal to 0 outside í µí±, belongs to í µí°¾; (b) the value of í µí± on some í µí±¥ is defined and equal to some í µí±¦ if and only if there exists some í µí± ∈ í µí± such that í µí»¼(í µí±) = í µí±¥ and í µí¼(í µí±) = í µí±¦. (Using the terminology from [1], one may say that í µí± is the set of all computation records for the function í µí± and all possible inputs; the functions í µí»¼ and í µí¼ are defined on all computation records and extract the input and output respectively.) 3. (Programs axiom) There exist a binary function í µí°¹ ∈ í µí°¾ that is universal for the unary functions in í µí°¾. This means that for every unary function í µí± ∈ í µí°¾ there exists some í µí± such that the function í µí°¹(í µí±, ⋅) coincides with í µí±
Priority arguments and separation problems
No full textTranslation made by the author in 2018International audienceDifferent constructions in the recursion theory use the so-called priority arguments. A general scheme was suggested by A.~Lachlan. Based on his work, we define the notion of a priority-closed class of requirements. Then, for a specific priority construction, we need to check only that all requirements we want to satisfy belong to some priority-closed class (defined in game terms). This game version of Lachlan's approach is used to present some results about recursively inseparable sets obtained by the author
Transducteurs et arborescences : études et réalisations de systèmes appliquées aux grammaires transformationnelles
No full textUniversité : Université scientifique et médicale de GrenobleTransducteur
Transduction d'arborescences : application aux manipulations de formules sur ordinateur
No full textUniversité : Université scientifique et médicale de GrenobleTransductio
Sur des problèmes de décomposition d'un graphe, liés à l'implantation
No full textUniversité : Faculté des sciences de l'Université de Grenobl
Etude des décompositions d'un réseau
No full textUniversité : Faculté des sciences de l'Université de Grenobl