Ce séminaire a lieu le vendredi de 16h15 à 18h15 (2 heures), à Chevaleret en salle 0C2.
Il s'agit d'exposés pouvant intéresser un public large, c'est-à-dire des étudiants ne suivant pas nécessairement le cours du MPRI le plus proche du sujet abordé.
Le planning des prochaines séances est
Vendredi 12 janvier 2007 :Giuseppe Longo (LIENS, CNRS et ENS de Paris)
Titre :Calculabilité et prédictibilité dynamique.
Résumé :
introduction informelle à la structure de la détermination classique, à partir du grand théorème des trois corps de Poincaré ;
rôle de la mesure en physique et dans toute tentative de transformer un processus naturel en calcul ;
la notion mathématique de déterminisme chaotique ;
imprédictibilité dynamique et indécidabilité computationnelle ;
l'aléatoire et la machine ;
le discret et le continu : les trajectoires et l?approximation digitale ;
exemples et résultats pour une dynamique unidimensionnelle (structure et calculabilité de la transition critique ; transitivité topologique et régimes chaotiques ; théorèmes d'indécidabilité/imprédictibilité).
Références (voir: http://www.di.ens.fr/users/longo )
Bailly F., Longo G. Mathématiques et sciences de la nature. La singularité
physique du vivant. Hermann, Paris, 2006 (avant-propos et introduction
téléchargéables)
Articles téléchargeables
Hoyrup M., Kolcak A., Longo G. Computability and the Morphological Complexity of some dynamics on Continuous Domains, invited survey, to appear.
Giuseppe Longo. Laplace, Turing and the "imitation game" impossible geometry: randomness, determinism and programs in Turing's test. In Epstein, R., Roberts, G., & Beber, G. (Eds.). The Turing Test Sourcebook. Springer- Kluwer, 2007.
Francis Bailly, Giuseppe Longo. Randomness and Determination in the interplay between the Continuum and the Discrete. Submitted
Giuseppe Longo. Computer Modelling and Natural Phenomena. Invited Lecture, Proceedings of the European Software Engineering Conference and ACM SIGSOFT Symposium, Helsinki, Finland, September 1-5, ACM Proceedings, New York, 2003.
Planning 2005-2006
Le planning des prochaines séances est
vendredi 2 décembre 2005 : Gérard Berry, Le modèle synchrone et ses applications logicielles et matérielles.
Vendredi 3 février 2005 :Igor Walukiewicz (LaBRI, CNRS et Université Bordeaux 1)
Titre :Jeux pour la vérification.
Résumé : We will discuss applications of two player path-forming games on
graphs. We will give an overview of problems in verification and
synthesis were games play a fundamental role.
In what concerns verification, we will mostly concentrate on the
model-checking problem, that is the problem of verifying if a given
formula holds in a given state of a given model. We will discuss a
close connection between this problem and the problem of deciding a
winner in some games. This connection turns out to be very robust and
of great help even in extensions such like pushdown systems or
probabilistic concurrent games.
For the synthesis part, we will see that, here too, we can reduce
synthesis problems to problems of solving games. Unlike for
model-checking, there are many different approaches to the synthesis
problem varying significantly, at least at the first sight. Among
others, we will discuss a proposal of an extension of the mu-calculus
that is capable of expressing in a unified way many of the problems
found in the literature.
Time permiting we will consider some recent generalizations. We will
present results on various non-regular winning conditions. We will
also discuss extensions of the game model both to probabilistic and to
multi-player settings.
Vendredi 10 février 2005 :Frank D. Valencia (LIX, CNRS et École Polytechnique)
Titre :On the Expressiveness of Infinite Behavior and Name Scoping in CCS.
(joint work with Gerardo Schneider and Pablo Giambiagi)
Résumé : In the literature there are several CCS-like process calculi differing in the constructs for the specification of infinite behavior and in the scoping rules for channel names. In this talk I will present various representatives of these calculi based upon both their relative expressiveness and the decidability of divergence. Two calculi are regarded equally expressive iff for every process in each calculus, there exists a weakly bisimilar process in the other.
I shall provide weak bisimilarity preserving mappings among the various variants, and show that in the context of relabeling-free and finite summation calculi: (1) CCS with parameterless (or constant) definitions is equally expressive to the variant with parametric definitions. (2) The CCS variant with replication is equally expressive to that with recursive expressions and static scoping. We also state that the divergence problem is undecidable for the calculi in (1) but decidable for those in (2). The results are obtained from (un)decidability results by Busi, Gabbrielli and Zavattaro, and by showing the relevant mappings to be computable and to preserve divergence and its negation. From (1) and the well-known fact that parametric definitions can replace injective relabelings, I will show that injective relabelings are redundant ( i.e., derived) in CCS (which has constant definitions only).
