(Exposé en deux parties : 04/10 et 11/10.) Dans ces exposés, on étudie l'existence de certains types de l'inégalité de Lojasiewicz sur des domaines non-compacts et de l'inégalité de Lojasiewicz globale pour les applications polynomiales de plusieurs variables. Partie I: on montre que sous certaines conditions de non-dégénérescence au sens de Khovanskii, l'inégalité de Lojasiewicz globale existe.
We give here an effective proof of Hilbert's nullstellensatz and Krivine-Stengle's positivestellensatz using the cut elimination theorem for sequent calculus. The proof is very similar to the current techniques in constructive algebraic geometry by Henri Lombardi, but seems more modular. In the case of the positive stellensatz, we think we prove a more general result than the original one, thanks to a new notion of justification of positiveness: PBDD (polynomial binary decision digram). It allows both to recover Krivine-Stengle's justification, but also another one which seems to require lower degree. We apply the same techniques to the nullstellensatz for differentially closed field and show that the proof is almost unchanged. Remark: here we do not provide bound, but an effective algorithm (implemented in OCaml) to build the wanted algebraic equality. Nevertheless, we discuss how bound could probably be obtained. We also do not deal effectively with the axiom of algebraic/real closure. Those are eliminated using standard model theory.
Le périmètre anisotrope mesure différemment les parties du bord, en rapport avec leur orientation. Par conséquence, les frontières des formes minimisant le périmètre anisotrope sous contrainte de volume vont avoir certaines directions privilégiées. La question est de trouver numériquement des partitions d'un ouvert en cellules d'aire prescrite, et qui minimise la somme des périmètres anisotropes des cellules. Les résultats numériques sont basés sur une approche par Gamma convergence, généralisant le théorème de Modica-Mortola en anisotrope/multiphase.
``The Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess'' (Wikipedia). This system is widely used to rank sport teams, online games, journals for instance. The Elo model studied is a Markov chain. When the players are numerous and interact a lot we derive a new continuous model: a kinetic equation with a mean field velocity. The asymptotic behavior of the ratings for large time, which is an important issue for the validity of the rating system, is studied. The idealistic case when all players are compared yields an exponential rate to the true rating independently of the initial rating. The realistic and complex case with only local interactions has several equilibria. The convergence holds to an equilibrium depending on the intial ratings but with no rate. What does it mean for this rating system? Some consequences and some open problems will be given.
A benefit of abstract computability – which is the main subject matter of this talk – is that it allows the explicit unification of complexity and computability. Understanding the broader geography of these subjects is important for a number of reasons: it brings new perspectives to an old subject and it allows new tools to be brought to bear on old problems.
Abstract computability defines timed sets''. Significantly, this mimics precisely what complexity theorists actually do. The abstract approach, however, has the advantage of removing conceptual clutter and clarifying the structure of what is happening. <br><br> Abstract computability is based round the notion of a Turing category: the talk will introduce this and the necessary related structures. <br><br> References:<br> Robin Cockett, Joaquin Diaz-Boïls, Jonathan Gallagher, Pavel HrubesTimed Sets, Functional Complexity, and Computability''
Robin Cockett, Pieter Hofstra ``Introduction to Turing Categories''
Les champs à divergence nulle ne peuvent conserver leur topologie de lignes de champs, lorsqu'ils sont diffusés par l'équation de la chaleur linéaire. Des équations de diffusion conservant la topologie, très non-linéaires, ont été proposées, notamment par H.K. Moffatt sous le nom de relaxation magnétique''. Elles ont pour solutions d'équilibre une classe très riche: à savoir toutes les solutions stationnaires des équations d'Euler des fluides incompressibles. En mélangeant des idées d'Ambrosio-Gigli-Savaré pour l'équation de la chaleur scalaire et la notion de solution dissipative des équations d'Euler proposée par P.-L. Lions, on parvient à définir un concept desolution dissipative'' pour la relaxation magnétique vers Euler, avec un théorème d'unicité ``fort-faible'' à la clef et d'existence globale de solutions.
Les matériaux ferromagnétiques sont de plus en plus utilisés dans l'industrie (peintures d'avions, mémoires d'ordinateurs, transformateurs....). Le comportement de l'aimantation dans ces matériaux est modélisée par l'équation très non linéaire de Landau-Lifschitz. On observe que l'aimantation a tendance à se structurer en domaines (larges zones dans lesquels l'aimantation est presque constante) séparés par des murs (zones fines dans lesquelles l'aimantation varie brusquement). Dans ses travaux précurseurs, Walker a décrit des profils de murs plans dans un modèles tri-dimensionnel de matériau ferromagnétique. Le but de l'exposé est de démontrer la stabilité des profils calculés par Walker vis à vis de l'équation de Landau-Lifschitz en dimension 3.
In this talk I will illustrate how to use basic results in Ehrhart theory to solve a problem on discriminants. I will introduce all the necessary notions such as Ehrhart polynomials and lattice polytopes. As it turns out, the problem will be reduced to a question about binomial coefficients.
A notion of test for intuitionistic type theory has been recently introduced by Peter Dybjer. It is meant to be the foundation for automatic testing tools that could be implemented in proof assistants such as Coq or Agda. Such tools would provide a way to test, at any time during the construction of a proof, if the current goal is typable in the context. The failure of such a test would mean that the goal is impossible to prove, and its success would corroborate the partial result. We investigate the possibility of extending the testing procedure to classical systems, and propose an interpretation of the testing procedure in term of Krivine's classical realizability.
Le 17 ème problème de Hilbert (1900) est le suivant: est ce qu'un polynôme positif en plusieurs variables est une somme de carrés de fractions rationnelles ? La réponse positive d'Artin (1927) est basée sur le lemme de Zorn: tout corps réel (où -1 n'est pas une somme de carrés) peut être ordonné. Artin note déjà qu'une construction effective de la somme de carrés serait souhaitable mais semble difficile. La difficulté vient des dénominateurs: quelles sont les bornes sur leurs degrés ? Un travail de Kreisel (1957) donne des bornes primitive récursives, mais pas élémentairement récursives (i.e. majorés par une tour finie d'exponentielles) Notre travail (en progrès) donne une tour de cinq exponentielles dans le nombre des variables et le degré du polynôme. (Travail en commun avec Henri Lombardi et Daniel Perrucci.)
Les transformations rigides (obtenues par composition de rotations et translations), lors qu’elles sont appliquées sur les imagesnumériques, sont généralement appliquées dans leur espace continu associé, nécessitant ensuite le recours à un procédé de digitalisation afin d’obtenir un résultat sur Z². Alternativement, nous proposons d'étudier ces transformations rigides dans un cadre totalement discret. En particulier, cette étude consiste à modéliser par une structure combinatoire (nommé, DRT graph) tout l'espace de paramètres de ces transformations sur les sous-ensembles de Z² de taille N × N. Ce graphe a une complexité spatiale de O (N^9). Nous décrivons cette structure combinatoire, et proposons également un algorithme permettant de la construire en temps linéaire par rapport à sa complexité spatiale. Le DRT graph peut être utilisé dans des applications de traitement d'images numériques, par exemple lors de procédures de recalage. Nous proposons ainsi des conditions pour lesquelles les images discrètes 2D préservent leurs propriétés topologiques pour toute transformation rigide. Nous en dérivons un procédé algorithmique permettant de vérifier l'invariance topologique des images par transformation rigide dans Z², où cette préservation n'est plus garantie contrairement à R². Cette étude est basée d'une part sur la notion de DRT graph, et d'autre part la notion de point simple. L'utilisation conjointe de ces deux notions permet notamment d'aboutir à une complexité en temps linéaire.
Etant donné un vecteur non nul n de R^d et deux réels mu et w, le plan discret de vecteur normal n, de décalage mu et d'épaisseur omega, noté P(n,mu,omega), tel que défini par J.-P. réveillès, est l'ensemble des points de Z^d satisfaisant la double inégalité 0 <= <n,x> + mu < omega où <.,.> désigne le produit scalaire usuel dans R^d. Pour k dans {0,...d-1}, deux points distincts x et y de Z^d sont des k-voisins s'ils ont au moins k coordonnées communes et leurs coordonnées diffèrent d'au plus 1. Lorsque x et y sont représentés par des cubes unités centrés sur les coordonnées entières, ces cubes partagent alors une facette de dimension au moins k. Une partie S de Z^d est k-connexe, si pour toute paire de points x et y dans S, il existe dans S un chemin x=x_1,...,x_q=y formé de k-voisins. Le problème qui nous intéresse est, étant donnés un vecteur normal n et un décalage mu, de déterminer l'ensemble des valeurs de l'épaisseur omega pour lesquelles le plan P(n,mu,omega) est k-connexe. Nous nous intéressons plus particulièrement au cas où k=d-1, c'est à dire à la connexité par face. Cet ensemble est alors un intervalle infini à droite dont la borne inférieure est appelée épaisseur de connexité de n avec décalage mu et notée Omega(n,mu). Cette épaisseur peut être calculée grâce à un algorithme simple connu sous le nom d'algorithme totalement soustractif (Fully Subtractive Algorithm). Par définition, le plan P(n,mu,omega) est non connexe si omega < Omega(n,mu) et connexe si omega > Omega(n,mu). La question qui se pose alors est celle de la connexité de P(n,mu,Omega(n,mu)). Ce plan est presque toujours non connexe mais peut être connexe si la suite de vecteurs calculée par l'algorithme a une certaine propriété déterminée par Kraaikamp et Meester et qui n'est satisfaite que pour les vecteurs appartenant à un certain fractal de mesure nulle. La question de la connexité de P(n,mu,Omega(n,mu)) lorsque n appartient à ce fractal a été résolue dans un cas particulier en collaboration avec V. Berthé, D. Jamet et X. Provençal. Nous résolvons ici le cas général. Le déroulement de l'algorithme peut être décrit par un mot infini Delta sur l'alphabet {1,...,d}. A partir de ce mot, nous construisons une suite de sous-ensembles de Z^d qui, entre autres propriétés, sont connexes. Nous montrons que la limite de cette suite, appelée clôture palindromique géométrique itérée de Delta, est en fait P(n,0,Omega(n,0)) prouvant ainsi que ce plan est connexe. Nous exhibons également certaines valeurs particulières du décalage mu pour lesquelles P(n,mu,Omega(n,mu)) est non connexe. Le cas général lorsque mu est quelconque reste une question ouverte. (E. Domenjoud & L. Vuillon)
My research focuses on distributed programming models, more precisely using objects and components. In this area, I provided tools easing the programming of large-scale distributed applications and verifying their correct behaviour. To facilitate the programming of distributed applications, I contributed to the design and the development of languages with a high level of abstraction. My work aims to provide a strong model of programming languages, libraries, and runtime environments to the developer, and to guarantee the safe behaviour of distributed applications. In the OASIS team, we contributed to the definition of a distributed component model - the GCM (Grid Component Model) -, to its formalisation, and to its use for programming adaptive or autonomous components. After a short introduction to the principles of distributed computing and to the use of formal methods in this area, this talk will provide an overview of those aspects focusing on the programming models. I will conclude with a focus on a couple of my current research topics that include distributed algorithms for peer-to-peer systems, and programming on multicore and distributed architecture.