Nous étudions des arbres binaires de recherche construits à partir des suites de Weyl, n * theta mod 1, où theta est irrationnel.
Mots-clefs: suite de Weyl, arbre binaire de recherche, approximation diophantienne, génération de suites aléatoires, analyse probabiliste, hauteur des arbres.
The transitive coercing semantic model for the execution of the MONSTR generalised term graph rewriting language is defined. Of all the operational semantics for MONSTR that one might consider, this one has the cleanest properties. Under intuitively obvious conditions for executions involving redexes permitted to overlap sufficiently to allow the programming of deterministic synchronisations, and despite the failure of exact subcommutativity, a Church-Rosser theorem is proved to hold up to markings and garbage.
Advances in hardware, software, and coding standards for digital media have now made the delivery of multimedia information a standard component of many systems. Unfortunately, the pace of this technological development, coupled with strong commercial competition between leading vendors, has meant that little consensus has emerged over the design of programming interfaces to allow the creation, manipulation, and presentation of such data. PREMO (PResentation Environments for Multimedia Objects) is a new ISO Standard, to be published in 1998, that defines a middleware framework encompassing synchronization, the management of distributed media resources, and the seamless integration of data and processes from disparate application areas. This presentation gives an overview of the concepts underlying PREMO and the approach by which the standard utilises these concepts to address key aspects of multimedia systems design.
PM2 (Parallel Multithreaded Machine) est un environnement de programmation parallèle dont l'objectif est de fournir à la fois un cadre évolué de conception pour le développement d'applications, mais aussi un support exécutif efficace. Nous présenterons dans la première partie de l'exposé les caractéristiques principales du modèle de programmation PM2 qui sont principalement issues de la thèse de Raymond Namyst.
La seconde partie de notre présentation concernera plus précisement les récentes évolutions de PM2 et nos travaux autour des réseaux à haut débit. L'approche que nous avons choisie pour PM2 High Perf s'appuie sur une interface de communication générique (nom de code: Madeleine) qui nous permet de porter efficacement PM2 sur des réseaux à haut débit comme Myrinet en utilisant les couches de communication les plus efficaces. Des projets de développements autour des réseaux à haut débit MPC (LIP6) et SCI (Action incitative INRIA) sont également en cours ou sur le point de démarrer.
One of the exciting developments in complexity theory is the discovery of a very intimate connection between computational complexity and logic. This intimate connection was first discovered by Fagin, who showed that the complexity class NP coincides with the class of properties expressible in existential 2nd-order logic. Although the relationship between descriptive and computational complexity is intimate, it is not without its problems. Indeed, there is a fundamental mismatch between computational devices and complexity, already noted by mathematicians like Tarski and Harvey Friedman: while computational devices work on encodings of problems, logic is applied directly to the underlying mathematical structures. As a result, machines are able to enumerate objects that are logically unordered. For example, while we typically think of the set of nodes in a graph as unordered, it does become ordered when it is encoded on the tape of a Turing machine. This "impedance mismatch" does not pose any difficulty in the identification of NP with existential 2nd-order logic since the logic can simply assert the existence of the desired order. The mismatch with logic becomes apparent, however, at complexity classes below NP. For example, the relationship between the class P and fixpoint logic is more complicated as a result of the mismatch. It is only when we assume built-in order that we get that P coincides with the class of properties expressible in fixpoint logic.
We present a device operating directly on structures, without encoding, called relational machine. The relational machine yields a new notion of complexity, quite different from classical computational complexity, which we call relational complexity. We show natural correspondences between relational complexity classes and logics, without any order assumption. For example, relational polynomial time corresponds precisely to the fixpoint queries, and relational polynomial space yields the while queries. Moreover, relational machines help overcome the "impedance mismatch" between logic and classical complexity, by acting as a mediator between logic and classical devices. A typical result of this type is that
This work is largely motivated by the study of database query languages and their complexity. Database queries are posed against an abstract interface, so they lead to computations more accurately modeled by relational machines than classical devices. In particular, using the relational machine, we obtain results which point to new possibilities for optimizing queries.
This talk is based on joint work with Serge Abiteboul, and partly with Kevin Compton and Moshe Vardi.