Let $A \subset \R^n$ be a set-germ at $0 \in \R^n$ such that $0 \in \overline{A}$. We say that $r \in S^{n-1}$ is a direction of $A$ at $0 \in \R^n$ if there is a sequence of points ${ x_i } \subset A \setminus { 0 }$ tending to $0 \in \R^n$ such that ${x_i \over | x_i |} \to r$ as $i \to \infty$. Let $D(A)$ denote the set of all directions of $A$ at $0 \in \R^n$. Let $A, \ B \subset \R^n$ be subanalytic set-germs at $0 \in \R^n$ such that $0 \in \overline{A} \cap \overline{B}$. We study the problem of whether the dimension of the common direction set, $\dim (D(A) \cap D(B))$, called the {\em kissing dimension} of $A$ and $B$ at $0 \in \R^n$, is preserved by a bi-Lipschitz homeomorphism. We show that in general it is not preserved. We prove that the kissing dimension is preserved if the images of the subanalytic sets under consideration are also subanalytic. In particular, if two subanalytic set-germs are bi-Lipschitz equivalent, then their direction sets must have the same dimension.
En partant d'une structure généralisant les graphes de transitions et les simulations, je montrerai comment relier les notions de programmes (ceux de la vraie vie) et de fonctions continues (celles de la topologie constructive). Ceci donne un contenu concret à la 171 topologie formelle 187 de Giovanni Sambin et peut-être vu comme une extension de l'isomorphisme de Curry-Howard. De plus tous les résultats peuvent être développés dans la théorie des types dépendants 171 à la suédoise 187. Plus généralement, la notion utilisée permet de décrire tout phénomène interactif entre un utilisateur et son environnement. La structure résultante permet, entre autre, de donner un modèle non-trivial du lambda-calcul différentiel et semble ainsi relier deux visions des calculs de processus. (??)
We prove the correctness of an original method for generating components that capture the occurrence of events, and monitor logical and temporal properties of hardware/software embedded systems. The properties are written in PSL, under the form of assertions in declarative form. The method is based on a library of primitive digital components for the PSL temporal operators. These building blocks are interconnected to construct complex properties, resulting in a synthesizable digital module that can be properly linked to the digital system under scrutiny.
Le lambda mu calcul symétrique (i.e. le calcul où on a ajouté la règle mu' duale de mu) est fortement normalisable dans le cas typé. Pourtant quand on ajoute la règle rho qui semble n'être qu'une règle de simplification, la forte normalisation est perdue. On garde cependant la faible normalisation. C'est ce qu'on montrera dans cet exposé.
(Travail commun avec C. Boubel et P. Mounoud)
Nous étudions les feuilletages de dimension 1 sur les variétés compactes de dimension 3 dont l’holonomie préserve une métrique lorentzienne transverse. Sous une hypothèse de complétude, nous les classifions et nous en déduisons la classification duale pour les feuilletages de codimension 1 de type temps qui sont totalement géodésiques et géodésiquement complets. Nous donnons aussi un exemple exotique de feuilletage dans le cas non complet.
Dans le cadre des grammaires catégorielles abstraites (ACG) introduites par Ph. de Groote, on peut faire des traductions entre différentes structures linguistiques, par exemple syntaxiques et sémantiques. Initialement conçu sur la base du lambda-calcul linéaire utilisé en linguistique, l'expressivité se trouve limitée notamment en sémantique, où l'on souhaiterait utiliser plusieurs fois une même variable. L'idée est alors d'introduire de l'intuitionisme, et donc un lambda-calcul avec deux types de variables et deux types de flèches (intuitionnistes et linéaires). Il est alors naturel de se demander quel peut être le type principal de termes de ce calcul, et quelles sont ses propriétés. Une difficulté provient du fait que lors de la recherche du type principal, des flèches sous-spécifiées peuvent apparaître, qui peuvent indifféremment être remplacées par les flèches linéaires ou des flèches intuitionistes. Pour ne pas compliquer ce lambda-calcul, il serait agréable de trouver des fragments pour lesquels on pourrait donner une notion de type principal sans flèche sous-spécifiée. Dans le cas général nous verrons que c'est impossible, mais que pour deux cas, le cas eta-long et le cas linéaire, nous avons un résultat.
Les jeux simultanés sont des objets représentant le scénario informel suivant : des agents effectuent simultanément chacun un choix parmi un ensemble (propre à chaque agent) de choix possibles. En fonction des tous ces choix, on attribue alors un gain à chaque agent. Et c'est tout, le jeux est terminé. Nash a défini une notion d'équilibre dans ces jeux mais il existe des jeux sans équilibre. Si les agents et les choix sont en nombre fini, Nash a montré qu'on pouvait construire d'un jeu une version "probabilisée" qui, elle, possède un équilibre. J'espère montrer lors de ce groupe de travail que l'introduction des probabilités n'était pas la seule solution envisageable. Deux directions possibles sont : 1) Introduire le non déterminisme sans proba. 2) Considérer la structure "la plus générale" dans laquelle on peut définir les équilibres à la Nash et insister sur l'aspect dynamique qui mène à la notion d'équilibre. Dans les deux cas, les concepts sont plus simples que les proba et les équilibres sont calculables. De plus, les ensembles d'équilibres possèdent des propriétés algébriques alors que les équilibres probabilistes sont peu structurés.
Notion of density is used when there is a need of quantitative considerations on countable sets. It is known fact that it is impossible to construct uniformly distributed probabilistic measure on such set. By now, standard approach to deal with this problem is to consider asymptotic behavior of probabilities in finite subsets of elements of bounded size. The well known results of such approach are 0-1 laws in logic. In the theory of formal languages notion of density was introduced by Berstel. First approaches were focused on regular languages and exploited the theory of formal power series. Natural extension is the notion of conditional density. For any language L let l_n denote number of words of length n in L. Let L,S be languages over finite alphabet such that S is a subset of L. Let p_n denote probability that randomly and uniformly chosen word from L of length not greater than n belongs to S. Language S has conditional density in L if and only if there exists the limit of p_n. Many problems, concerning asymptotic properties of predicate logic formulae with bounded number of variables, can be rephrased in the theory of languages using the above definition. For the classes of grammars C,D the problem of having conditional density is defined as follows: Given two grammats G_L belonging to C and G_S belonging to D, decide whether L(G_S) has conditional density in L(G_L). In my talk I am going to present my result concerning decidability of the problem of conditional density for several classes of grammars.
Je donnerai les définitions de bases et la preuve de subject-reduction de mon système.
Les calculs de processus mobiles, tels que le pi-calcul, sont bien adaptés à la description des systèmes distribués comportant des canaux de communication mobiles et des processus qui sont créés/détruits dynamiquement. En revanche, les algèbres de processus classiques, telles que CCS, CSP ou ACP, ne permettent pas une description directe de la mobilité, mais bénéficient d'environnements de simulation et de vérification plus développés. Dans cet exposé, je présenterai une traduction d'un fragment du pi-calcul vers LOTOS et E-LOTOS (des normes ISO issues de CCS et CSP), qui permet de simuler la communication sur des canaux mobiles. Je préciserai également quelques pistes de recherche pour étendre cette traduction vers des fragments plus larges du pi-calcul.
Les surfaces elliptiques propres réelles, c’est-à-dire les surfaces dont la dimension de Kodaira est égale à 1, constituent la seule classe de surfaces algébriques réelles de type spécial dont la classification topologique n’est pas achevée.
Quand le nombre de Hodge h0,1(X) est nul, c’est-à-dire que la surface elliptique X est régulière, nous donnons une réponse complète à la question des valeurs possibles des nombres de Betti de la partie réelle, pour chaque famille complexe. En particulier, nous retrouvons les réponses bien connues à cette question dans le cas des surfaces elliptiques rationnelles et les surfaces K3 elliptiques.
Séance informelle sur la ludique ou la complexité implicite ou les relations entre ludique et calculs de processus.
About 10 years ago, Boris Shapiro and Michael Shapiro made a remarkable conjecture about real solutions to geometric problems coming from the classical Schubert calculus. While the conjecture remains open, there is truly overwhelming computational evidence supporting it, and Eremenko and Gabrielov proved it for Grassmannians of 2-planes, where the conjecture is the appealing statement that a rational function with only real critical points must be real.
In my talk, I will introduce the Shapiro conjecture and discuss what we know about it. This includes a simple counterexample and a refinement which is supported by massive experimental evidence. This evidence includes tantalizing computations which suggest a strengthening: that a certain discriminant polynomial is a sum of squares, or more generally that it has such an algebraic certificate of positivity.
Un groupe de traces est le quotient d'un groupe libre par des relations de commutation entre certaines lettres. On peut représenter les traces par des tas de pièces colorées. Dans une première partie, nous étudions les groupes de traces d'un point de vue combinatoire et obtenons une formule explicite de la série génératrice d'un groupe de traces, comparable à la formule d'inversion de Möbius pour le monoïde de traces. Dans un deuxième temps, nous utilisons cette formule pour étudier le taux de croissance moyen asymptotique d'un tas de pièces colorées.