UNIVERSITE DE PARIS VII, UFR DE MATHEMATIQUES
  Séminaire général de Logique - Année 2000 - 2001

Je vais dans cet exposé donner quelques nouvelles caractérisations logiques de la classe des langages rudimentaires. La première caractérisation est basée sur une logique introduite par Parigot et Pelz pour caractériser logiquement la classe des langages des réseaux de Petri. Les autres sont basées sur des quantificateurs de comparaison de cardinalité.
Ces caractérisations nous ont inspiré pour donner un jeu, à la Fraïssé - Ehrenfeucht, qui donne un moyen pour prouver si oui ou non un langage est rudimentaire. L'utilisation de cette méthode pose deux problèmes qu'on expliquera.

Un oméga langage algébrique est un langage de mots infinis, sur un alphabet fini, qui est accepté par un automate à pile avec condition d'acceptation de Büchi ou de Muller. L'ensemble des mots infinis sur un alphabet fini étant muni de la topologie usuelle, on étudiera dans cet exposé les propriétés topologiques de ces oméga langages. En particulier on montrera qu'il existe des oméga langages algébriques qui sont analytiques mais non Boréliens. On en déduira une réponse à une question de Niwinski, donnant un exemple d'oméga puissance non borélienne d'un langage algébrique de mots finis.

On se donne une structure M dans un langage fini. Depuis Blum, Shub, Smale et Poizat on s'intéresse à la "complexité" des suites de relations définissables de M. Au niveau non uniforme les classes de complexité de telles suites se définissent en utilisant la taille des objets (formules sans quanteurs, circuits, formules existentielles et autres...) que l'on se permet pour définir ces suites. On présentera des resultats de séparation de ces classes ainsi que quelques exemples curieux. L'ingrédient principal étant les prédicats de verité et le paradoxe du menteur.

Soit G un groupe fini. Il y a manifestement un énoncé existentiel vrai dans G tel que G se plonge dans tout modèle de cet énoncé existentiel. On se propose d'examiner les groupes infinis qui possèdent cette proprieté (ou une de ses variantes)
Comme le lecteur l'observera notre problématique s'étend à d'autres classes de structures que le cadre des groupes - dans lequel on se place par commodité et pour obtenir des résultats.

Depuis 1974, de nombreuses classes de complexité ont été définies par la complexité logique de propriété de structures finies. Ainsi :
     - la hiérarchie polynomiale PH correspond aux formules du second ordre,
     - NP correspond aux formules existentielles du second ordre,
     - Monadic NP à ces formules où les quantifications existentielles se font sur des parties (relations unaires).
Ajtai, Fagin et Stockmeyer (2000) ont étudié diverses classes de complexité, toutes comprises entre Monadic NP et PH, et toutes définies par leur complexité logique.
Nous ferons un tour d'horizon de ces classes et des techniques utilisées pour étudier leurs relations mutuelles.

(se basant sur un travail signé Boughattas- Chinchilla-JPR : "BOOTSTRAPPING")
Une 1ère partie (courte) rappelle que les problèmes fonda- mentaux de Complexité (P différent de NP, collapse de la hiérarchie polynomiale PH, etc...) ; et ceux de la Cryptographie (difficulté de la factorisation des entiers, etc...) se ramènent pour la plupart (assez facilement dans certains cas - par theorèmes dans d'autres) à savoir construire des modèles non standard des entiers avec certaines proprietés.
La 2ème partie présente du neuf en matière de construction de ce type - basé sur les indiscernables et sur l'o-minimalité de la structure (R,+,.,exp) .
Finalement on expliquera pourquoi ce travail est intitulé "BOOTSTRAPPING" ; et comment le fait que la proprieté de Vapnik- Tchervonenkis est vraie dans (R,+,.,exp) offre des perspectives nouvelles à ces constructions.

Stationary set reflection has become a standard principle for combinatorial constructions in set theory. In this talk I will state the various principles and illustrate their use as well as state some recent joint results with S. Todorcevic. Most of the talk will be accessible to a general audience.

L'auto-test est une notion de test introduite par Blum, Luby et Rubinfeld au début des années 90. Dans ce formalisme un testeur doit estimer à moindre coût la fiabilité d'un programme vu comme boîte noire : le testeur doit etre plus simple que n'importe quel programme correct, et ne peut qu'évaluer le programme en des entrées qu'il choisit. Ainsi, un testeur ne peut ni simuler lui même le comportement d'un programme correct (ce qui ne ferait que déplacer le problème), ni accéder au source du programme qu'il teste (ce qui ne garantirait pas la validité du programme une fois implémenté). Contre toute attente, Blum et al. ont montré qu'il était possible de définir de tels testeurs, dits auto-testeurs, pour toute une série de programmes numériques. Mais plus surprenant, ils ont construit des auto-correcteurs capables de corriger efficacement tout programme faiblement erroné. Les applications de ce domaine sont à la fois théoriques et pratiques (testeurs implémentés). Nous présenterons dans cette exposé les concepts fondamentaux de l'auto-test et passerons en revue ses résultats majeurs. Nous terminerons en citant quelques axes de recherche que nous jugeons intéressants.

O. Chapuis, E. Hrushovski, P. Koiran et B. Poizat ont introduit une nouvelle théorie complète : la théorie limite des courbes génériques. Je présenterai cette théorie puis je montrerai que des courbes génériques de degré supérieur à exp(2r) ne peuvent pas être distinguées à l'aide d'une formule du premier ordre de rang de quantification inférieur à r. On en déduit aisément un algorithme de décision pour la théorie limite.

Références :
- O. Chapuis, E. Hrushovski, P. Koiran et B. Poizat. La limite des théories de courbes génériques. A paraître dans le Journal of Symbolic Logic. http://www.ens-lyon.fr/~koiran/publications.html
- Back-and-forth systems for generic curves and a decision algorithm for the limit theory, P. Koiran et N. Portier, A paraître dans "Annals of Pure and Applied Logic" http://www.ens-lyon.fr/~nportier/publi.html

Travail commun avec Rémy Malgouyres. Nous avons étudié la complexité algorithmique de problèmes usuels de géométrie discrète en 2D. La géométrie discrète consiste à étudier les propriétés topologiques d'objets géométriques discrets, tels que ceux rencontrés en analyse d'images ou en traitement d'images en informatique. Certaines opérations de base sont très courantes, comme déterminer si un sous-ensemble est connexe, ou étiqueter des composantes connexes. Les algorithmes d'amincissement sont aussi largement utilisés en reconnaissance des formes et en analyse d'images, et la notion d'amincissement topologique peut se modéliser par la notion de sous-homotopie. Enfin, la notion d'homotopie symétrique correspond intuitivement à la notion de déformation continue, et c'est aussi une notion très importante pour la reconnaissance de formes. Le but de ce travail est d'étudier la complexité algorithmique de ces opérations de base.
Nous avons d'abord montré que tous les problèmes étudiés se réduisent à celui de l'accessibilité dans une image 2D (i.e. le problème de déterminer si deux pixels dans une image binaire sont connectés dans cette image). Nous avons ensuite étudiée la complexité de ce dernier problème. Nous montrons qu'il est dans LogSpace. (On obtient comme corollaire le fait que tous les problèmes auxquels nous nous sommes intéressés sont dans LogSpace.) Ensuite, on en donne une borne inférieure, en montrant que ce problème est NC1-difficile. Enfin, on montre qu'aucun des problèmes de base que nous avons considérés dans ce travail ne peut être calculé en temps parallèle constant avec des ressources polynomiales (i.e. en utilisant une famille de circuits AC0).

Mots-clés: Complexité descriptive, modèles finis, temps linéaire, problèmes combinatoires

Résumé : On s'intéresse à certains liens étroits entre la compléxité algorithmique et la définissabilité logique.
         On montre d'abord combien la classe NLIN des problèmes reconnaissables en temps linéaire non déterministe (qui comprend la plupart des problèmes NP-complets usuels) est robuste de par ses caractérisations logiques (restriction de la logique existentielle du second ordre avec ses variantes : formes normales et extensions, par exemple par une forme restreinte de ferméture transitive).
         En second lieu, on s'intéresse aux problèmes, qu'on considère ici comme des ensembles de structures finis du premier ordre (par exemple des graphes vus comme structures (V,E) avec E relation binaire sur le domaine V des sommets), et on étudie la classe, notée VertexNLIN, des problèmes reconnus en temps non déterministe O(n) où n est la cardinalité du domaine (ex : pour un graphe, son nombre de sommets). Là encore, on montre la robustesse de la classe VertexNLIN, tant sur le plan logique qu'algorithmique. L'intérêt de cette classe est encore renforcé par le fait (qu'on justifiera) qu'elle contient nombre de propriétés de graphes, connexité, biconnexité, hamiltonicité, nonplanarité, etc, qui sont donc reconnaissables en temps non déterministe O(n), où n est le nombre de sommets du graphe considéré, donc éventuellement (pour les graphes denses), en temps sous-linéaire en la taille (= nombre d'arêtes) du graphe.
         Enfin, on fera un rapide bilan des classes etudiées et de quelques autres, tant en ce qui concerne leurs liens connus (inclusions/séparations) que leurs caractérisations logiques.
(travail commun avec C. Lautemann, F. Olive et S. Ranaivoson).

Lundi 2 avril - Alexei SOSSINSKY (Moscou) : Résultats récents d'indécidabilité en topologie.

Lundi 30 avril - Michel de ROUGEMONT (Orsay) : Définissabilité et Compression

A compression algorithm takes a finite structure of a class K as input and produces a finite structure of a different class K' as output. Given a property P on the class K defined in a logic L, we study the definability of property P on the class K'. We consider two compression schemas on unary ordered structures (words), compression by run-length encoding and the classical Lempel-Ziv.

First-order properties of strings are first-order on run-length compressed strings, but this fails for images, i.e. 2-dimensional strings. We present simple first-order properties of strings which are not first-order definable on strings compressed with the Lempel-Ziv compression schema.

We show that all properties of strings that are first-order definable on strings are definable on Lempel-Ziv compressed strings in FO(TC), the extension of first-order logic with the transitive closure operator. We define a subclass F of the first-order properties of strings such that if L is defined by a property in F, it is also first-order definable on the Lempel-Ziv compressed strings. We then present new results for other compression schemas, in particular for a random schema.

Lundi 7 mai - Deirdre HASKELL (McMaster), Lundi 14 mai - Dugald MACPHERSON (Leeds). Elimination of imaginaries in algebraically closed valued fields I and II.

Il est bien connu que la théorie des corps valués algébriquement clos n'admet pas la propriété de l'élimination des imaginaires dans un langage naturel pour les corps valués. On peut alors se demander s'il existe un langage avec des sortes pas trop compliquées où l'on a cette propriété. Par le travail récent de Haskell, Hrushovski et Macpherson on a pu répondre à cette question. Pour le premier exposé, D. Haskell expliquera l'idée de l'élimination des imaginaires, donnera quelques exemples et une description du théorème. Pour le deuxième exposé (en anglais) D. Macpherson donnera plus de détails en ce qui concerne la démonstration, et en particulier, il expliquera comment on code les modules, et les noyaux des fonctions définissables.

Lundi 21 mai - Gerhard HEINZMANN (Nancy II) : Poincaré et la Logique

Poincaré a été semi-intuitionniste, anti-logiciste et prédicativiste. Dans une première partie de ma conférence, je donne une description historique de sa position en esquissant le contexte des controverses avec Russell, Hilbert, Zermelo et Brouwer. Dans une deuxième partie, je reprend l'opinion répandue selon laquelle le mathématicien Poincaré n'aurait eu qu'une connaissance superficielle de la nouvelle logique : l'attitude négligeante de Poincaré s'explique par le fait que les différentes théories de la logique formelle n'expriment pas, selon lui, l'élément essentiel à la compréhension d'une démonstration mathématique. Je termine par l'indication de quelques exigences nécessaires à une logique pour la compréhension du raisonnement mathématique au sens de Poincaré.

La notion d'indiscernables qui apparaît classiquement dans le theorème d'Ehrenfeucht- Mostowski tisse des liens entre Combinatoire, Théorie des ensembles, Théorie des modèles ; et par ses applications elle touche à bien d'autres sujets (espaces de Banach par exemple). Elle est le thème de la "Journée" annoncée ici

DATE : Mardi 22 Mai de 10 heures à 12h (exposés 1 à 3) et de 14h à 16h (exposés 4 à 6)

LIEU : Chevaleret salle 0C5 (au rdc)

PUBLIC VISE : Logiciens et Utilisateurs de la Logique, ETUDIANTS en DEA ou en thèse de Logique, Philosophes

FORME : six exposés d'une demi-heure, par 6 renommés spécialistes qui se mettront en 4 pour vous faire assimiler ce qu'il faut savoir sur ce sujet porteur en Logique. Exposés séparés par des pauses d'un quart d'heure.

Exposé 1 (Chinchilla) : Théorèmes de partition et Indiscernables
Exposé 2 (Ressayre) : Indiscernables forts et Contrôle des quanteurs
Exposé 3 (Foreman) : Une preuve du théorème de partition d'Erdös-Rado
Exposés 4 et 5 (Velickovich et Todorcevic) : 0 dièze
Exposé 6 : (Mariou) Indiscernables et Théorie des modèles algébrique

CONTENU - Le 1er exposé dégage les points communs des théorèmes de partition en allant du cas fini à celui des grands cardinaux. L'exposé 2 applique les indiscernables aux systèmes d'Arithmétique liés aux fondements et à la Complexité Algorithmique. L'exposé 3 montre comment appliquer les principes de réflexion aux théorèmes de partition. Les exposés 4 et 5 exposent le noyau de l'application des indiscernables en Théorie des ensembles. Le dernier exposé aborde le passage de l'indiscernabilité à l'indépendance qui est au coeur de la Théorie des modèles.

Lundi 28 mai - Joël COMBASE (Paris I) : Théorème de l'ensemble parfait et Théorie des modèles

Une première partie propose une généralisation du théorème de Silver sur le nombre de classes d'équivalences d'une relation co-analytique, qui fait intervenir une notion de dépendance. Une deuxième partie utilise les propriétés du forking dans les théories superstables pour satisfaire les conditions d'application du théorème de la première partie.
On en déduit par exemple que si un modèle totalement borélien d'une théorie superstable est omega_1 saturé, alors il est saturé.

Jeudi 7 juin - Harvey FRIEDMAN (Ohio State U.) : Boolean relation theory.

Boolean relation theory is simply the study of the Boolean relations between one dimensional sets and their images under multivariate functions. This study naturally leads to a variety of statements equivalent to the 1-consistency of Mahlo cardinals of finite order, even in concrete settings in the integers which are subject to known quantifier elimination. In addition, there are classifications of large finite families of such statements (as to truth value) which can be proved to be correct with and only with the use of Mahlo cardinals of finite order. The compelling nature of the particular examples of Boolean relation theory cited is steadily improving. The state of the art will be presented in the lecture.

Lundi 11 juin - Zoé CHATZIDAKIS (Paris VII) : Théories asymptotiques de corps différentiels (Travail en commun avec E. Hrushovski).

Soit p un nombre premier, F_p le corps à p elements, et K(p) la cloture séparable du corps F_p(t). Il existe alors une (et une seule) dérivation D_p sur K(p) qui satisfasse D_p(t)=1.
Pour chaque p, nous considerons K(p) comme un corps muni de la dérivation D_p, et nous étudions la théorie T, consistant des énoncés du langage des corps différentiels {+,-,.,0,1,D} qui sont vrais dans presque tous les corps différentiels K(p). Nous montrons alors que la théorie T est \Sigma_2^0-complete. Plus précisément, étant donnée une \Sigma_2^0-formule a(x) du langage de l'arithmétique ({+,.,0,1,<}) il existe des formules universelle b(x) et existentielle c(x) telles que pour tout entier n nous ayons les équivalences suivantes:
(i) a(n) est vrai dans (N,+,.,0,1,<)
(ii) T prouve b(n)
(iii) T prouve c(n)
La preuve de ce résultat passe par une interprétation uniforme en p du corps F_p, avec la structure additionnelle induite par son identification avec un segment initial de N, et de plus la définition sur F_p d'"exponentielles modulo p".
Après avoir donne les définitions de base, nous donnerons quelques détails sur ces interprétations, et une idée de la preuve.

Lundi 18 juin - Murray MARSHALL (Saskatoon) Open problems in the theory of spaces of orderings

Every formally real field F has associated to it a reduced special group G = F^*/ \sum F^*2 (terminology of M. Dickmann) and a space of orderings (X,G) (my terminology) where X is the topological space of orderings of F. The two concepts are known to be essentially equivalent. There are a number of hard open problems in the theory of spaces of orderings (e.g., L. Bröcker's t-invariant problem; M. Coste's problem about mod 2^k representation in the reduced Witt ring of F) which would be answered positively if it were known that positive primitive formulas in the language of special groups which hold true on every finite quotient of G, hold on G as well. There is some evidence for this conjecture. The statement that a quadratic form over F is weakly isotropic is such a pp formula (by the local-global principle for weak isotropy due to L. Bröcker and A. Prestel). The characterization of the powers of the fundamental ideal of the reduced Witt ring of F in terms of signatures can also be reduced to such a pp formula (by the solution of the signature conjecture by Dickmann and Miraglia, using K-theoretic results of Voevodsky). Thus it would appear that even if the conjecture is false, it is still important to determine for which sorts of pp-formulas and which sorts of special groups it is true.

Lundi 25 juin - Francis OGER (Paris VII) : Théorie des modèles des pavages

Un pavage d'un espace vectoriel de dimension finie sur R est un recouvrement par des pavés disjoints, tous obtenus par translation à partir d'un ensemble fini de pavés élémentaires. Pour tout systeme fini de pavés élémentaires, on a un langage relationnel naturellement défini L tel que deux pavages soient équivalents à translation près si et seulement si les L-structures associées sont isomorphes. On montre que deux pavages ont les memes fragments bornés à translation près si et seulement si les L-structures associées sont élémentairement équivalentes.

Pour tous pavages P,Q, on pose P<=Q si tout fragment borné de P est équivalent à un fragment de Q à translation près. On montre que tout pavage est minoré par un pavage qui est minimal pour <=, et qu'un pavage est minimal pour <= si et seulement s'il contient une copie de chacun de ses fragments bornés au voisinage de chacun de ses points. Les pavages, généralement non périodiques, obtenus par la méthode de projection à partir d'un pavage périodique d'un espace de dimension supérieure, sont des exemples de pavages minimaux pour <=.

Enfin, on considère les familles W de pavages qui sont définies par des règles, dont chacune consiste à dire qu'un certain assemblage borné n'apparaît nulle part dans le pavage. Pour une telle famille, il existe un ensemble U d'énoncés universels de L tel que les modèles de U soient, à isomorphisme près, les réunions disjointes de pavages de W. Si W est définie par un ensemble fini de règles, et si les pavages de W sont non périodiques et minimaux pour <=, alors un seul énoncé universel suffit, et la théorie définie par cet énoncé est complète et superstable. Les pavages de Penrose et les pavages de Robinson sont des exemples de cette situation.

Les résultats ci-dessus sont démontrés, essentiellement, en prouvant que des résultats analogues sont vrais pour les L-structures, où L appartient à une certaine classe de langages relationnels.

Page maintenue par :  malod_at_logique.jussieu.fr