Research

Expressiveness of full first order constraints in the algebra of finite or infinite trees, with Dao Thi-Bich-Hanh, submitted to, CP2000, Singapore september 2000. Abstract. We are interested in the expressiveness of constraints represented by general first order formulae, with equality as unique relational symbol and functional symbols taken from an infinite set F. The chosen domain is the set of trees whose nodes, in possibly infinite number, are labeled by elements of F. The operation linked to each element f of F is the mapping (a1,...,an) |-> b, where b is the tree whose initial node is labeled f and whose sequence of daughters is a1,...,an. We first consider constraints involving long alternated sequences of quantifiers EAEA... . We show how to express winning positions of two-partners games with such constraints and apply our results to two examples. We then construct a family of strongly expressive constraints, inspired by a constructive proof of a complexity result by Pawel Mielniczuk. This family involves the huge number alpha(k), obtained by evaluating top down a power tower of 2's, of height k. With elements of this family, of sizes at most proportional to k, we define a finite tree having alpha(k) nodes, and we express the result of a Prolog machine executing at most alpha(k) instructions. By replacing the Prolog machine by a Turing machine we rediscover the following result of Sergei Vorobyov: the complexity of an algorithm, deciding whether a constraint without free variables is true, cannot be bounded above by a function obtained by finite composition of elementary functions including exponentiation. Finally, taking advantage of the fact that we have at our disposal an algorithm for solving such constraints in all their generality, we produce a set of benchmarks for separating feasible examples from purely speculative ones. Among others we solve constraints involving alternated sequences of more than 160 quantifiers. cpe.pdf cpe.ps.zip

Pouvoir d'expression des contraintes du 1ier ordre dans l'algèbre des arbres finis ou infinis, avec Thi-Bich-Hanh Dao, version française du papier précédent. Résumé. Nous nous intéressons au pouvoir d'expression de contraintes représentées par des formules générales du premier ordre avec pour seul symbole de relation l'égalité et pour symboles de fonction les éléments d'un ensemble infini F. Le domaine choisi est l'ensemble des arbres dont les noeuds, en nombre éventuellement infini, sont étiquetés par les éléments de F. L'opération associée à chaque élément f de F, d'arité n, est l'application (a1,...,an) |-> b, où b est l'arbre dont le noeud initial est étiqueté f et dont la suite de fils est a1,...,an. Nous examinons tout d'abord des contraintes faisant intervenir de longues suites alternées de quantificateurs EAEA.... Nous montrons comment exprimer les positions gagnantes d'un jeux à deux adversaires par de tels contraintes et appliquons nos résultats à deux exemples de jeux. Nous construisons ensuite une famille de contraintes très expressives, inspirée d'une démonstration constructive d'un résultat de complexité de Pawel Mielniczuk. Cette famille fait intervenir le nombre immensément grand alpha(k), obtenu en évaluant de haut en bas une tour de puissances de 2 de hauteur k. Elle nous permet, en une contrainte de longueur au plus proportionnelle à k, de définir un arbre ayant exactement alpha(k) noeuds ou d'exprimer le résultat d'une machine Prolog exécutant au plus alpha(k) instructions. En remplaçant la machine Prolog par une machine de Turing nous retrouvons le résultat suivant de Sergei Vorobyov : la complexité d'un algorithme décidant si une contrainte sans variable est vraie, ne peut être majorée par une fonction obtenue par composition finie de fonctions élémentaires (comprenant l'exponentiation). Enfin, profitant du fait que nous disposons d'un algorithme pour résoudre de telles contraintes dans toutes leurs généralités, nous effectuons un ensemble de benchmarks permettant de départager les exemples réalisables des exemples purement spéculatifs. Nous arrivons notamment à résoudre des contraintes faisant intervenir des suites alternées de plus de 160 quantificateurs. cpf.pdf cpf.ps.zip

A related work to which a have collaborated:

Thi-Bich-Hanh Dao, Résolution de contraintes du premier ordre dans la théorie des arbres finis ou infinis,  Thèse de doctorat, Université de la Méditerranée, Marseille, décembre 2000 tc4dec.pdf tc4dec.ps.gz

Optimal Narrowing of a Block of Sortings in Optimal time, with Noëlle Bleuzen-Guernalec, January 1999.  Let D be a totally ordered set. Call n-block, a Cartesian product of n closed and possibly empty intervals of D.  Let  sort  be the set of all  2n-tuples of elements of D of the form  (x1,...,x2n), where  (xn+1,...,x2n)  is the n-tuple obtained by putting the terms of the n-tuple (x1,...,xn)   in non-decreasing order.  We present and justify an algorithm of complexity O(n log n)  which, given a 2n-block  a, computes a 2n-block which, by inclusion, is the smallest block containing the  intersection of  tri  with a. We show that this complexity is optimal. This paper is a preliminary version of: Optimal Narrowing of a Block of Sortings in Optimal time, in Constraints: an International Journal, Kluver, 5, 85--118, 2000. janu99.ps.zip janu99.pdf

Résolution naïve de contraintes non linéaires. Nous étudions un algorithme naïf et incomplet pour résoudre des systèmes non linéaires de contraintes construits à partir de variables réelles, de constantes rationnelles, des opérations -, +, times et des relations geq, >, =, neq. Par résoudre un système S, nous entendons deux choses: tout d'abord, décider si S admet au moins une solution, ensuite, déterminer l'ensem\-ble des équations de la forme x=constante qui sont impliquées par S. Dans une phase préliminaire on introduit des variables intermédiaires pour scinder S en deux sous-systèmes, l'un linéaire, l'autre non-linéaire et constitué d'équations de la forme z=x times y o\`u x, y et z sont des variables. L'algorithme naïf proprement dit se résume à répéter deux actions jusqu'à ce que le système n'évolue plus ou que la partie linéaire n'ait plus de solutions. La première action consiste à résoudre la partie linéaire de S. La deuxième action consiste à considérer les équations de la forme x=constante qui sont impliquées par la partie linéaire de S et à remplacer dans les membres droits des équations non-linéaires de S chacun des x par la constante correspondante. On montre que l'algorithme naïf devient un algorithme complet si l'on se place dans la structure non-standard suivante des réels: La sémantique de la multiplication est modifiée en considérant que le produit de deux nombres irrationnels est un élément étrange omega distincts de tous les réels. Les opérations sont prolongées en considérant que le résultat est omega dès que l'un des arguments est omega. Une entorse à ce principe est faite pour la multiplication par zéro qui produit toujours zéro. Toutes les relations, y compris la relation =, sont considérées comme satisfaites dès que l'un au moins des arguments est omega. Les rationnels sont conservés comme constantes et les variables sont astreintes à ne jamais prendre la valeur omega. mulnaive.ps.zip mulnaive.pdf

Related work to which I have collaborated:

Ian Gambini, Quant aux carrés carrelés, Thèse de doctorat, Université de la Méditerranée, décembre 1999. Résumé. Cette thèse est consacrée au calcul de découpages d'un carré en carrés de tailles différentes. Tout d'abord nous reprenons la méthode classique : énumération de graphes planaires représentant les emplacements des carrés les uns par rapport aux autres et, pour chaque graphe, résolution d'un système linéaire donnant les dimensions des carrés sous forme de nombres rationnels. La difficulté essentielle est de travailler en précision infinie. Pour celà nous étudions différentes méthodes qui permettent de contrôler la taille d'un dénominateur commun à tous les nombres rationnels manipulés. Pour un entier donné nous obtenons ainsi toutes les décompositions en carrés. Notre programme retrouve les solutions connues pour n entre 21 et 26. En fait ce problème de découpage est un problème en nombres entiers : les tailles des différents carrés sont toutes commensurables (dans des rapports rationnels). Il est donc possible de calculer les découpages par énumération d'entiers représentant des tailles de carrés. C'est l'objet du reste de la thèse. Nous établissons tout d'abord quelques propriétés concernant les dimensions entières des carrés : entre autre, les carrés dans les coins sont de taille supérieure à 8 et ceux sur les bords de taille supérieure à 4. Ceci nous permet de développer un algorithme opérationnel qui, étant donné la taille d'un carré, trouve tous ses découpages possibles. Nous arrivons ainsi à découper des carrés de taille allant jusqu'à 130 et retrouvons les découpages minimaux bien connus et notamment celui en 21 carrés. Nous développons alors un deuxième algorithme beaucoup plus efficace mais incomplet : il énumère des découpages particuliers. Nous obtenons plus de 30000 solutions parmi lesquelles figure toujours le fameux découpage en 21 carrés. Avec quelques modifications cet algorithme nous fournit des solutions à deux problèmes connexes : la décomposition en carrés de tailles distinctes d'un cylindre et aussi d'un tore. Dans le premier cas le cylindre est de hauteur et de circonférence égale et les carrés sont formés de deux arcs de cercle et de deux segments de même longueur. Dans le deuxième cas, les côtés des carrés sont des arcs de cercle de dimensions angulaires égales. carres.ps.zip carres.pdf

Bruno Gilleta, Solving the three-dimensional Pentamino Puzzle. Abstract. Pentaminoes are pieces made of 5 connected unit cubes lead on a plane surface. Their 12 different shapes look like the 12 letters F, I, L, P, N, T, U, V, W, X, Y, Z. We are interested in all the different ways of putting these 12 pentaminoes in a box having a volume of 60 unit cubes. We express the different pentaminoes configurations as the solutions of a natural set of constraints on unknown integers and we present an algorithm for solving our constraints by iterations of local narrowing and by splitting intervals in disjoint intervals. Benchmarks show that a classical enumerative algorithm is still the most efficient way to solve our problem. However, our smaller search spaces show that we are working on the right track. misc99.ps.zip misc99.pdf

Bruno Gilleta, Resolution du puzzle tridimensionnel des pentaminos, submitted to, Journées Francophones de Programmation Logique et Programmation par Contraintes (JFPLC'2000), Marseille, June 2000, proceedings to be published by Hermes Science Publications. Résumé. Les pentaminos sont des pièces connexes form'es de 5 cubes unitaires assembl's à plat. Il en existe 12 différents et leurs formes ressemblent aux 12 lettres F, I, L, P, N, T, U, V, W, X, Y, Z. Nous nous intéressons à placer de toutes les façons possibles ces 12 pentaminos dans un parallélépipéde rectangle d'un volume de 60 cubes unités. Nous présentons un ensemble naturel de contraintes sur les nombres entiers dont les solutions donnent les différentes façons de placer les pentaminos et présentons un système pour résoudre nos contraintes par itérations de réductions locales et par coupures d'intervalles en intervalles distincts. Des benchmarks montrent qu'un algorithme énumératif classique reste de loin la méthode la plus rapide mais le fait que nos arbres de recherche soient de taille inférieure montrent que nous sommes dans la bonne voie. jfplc2000.ps.zip jfplc2000.pdf

An Introduction to Prolog III, in Communications of the ACM, vol. 33, no. 7, July 1990. Abstract. The Prolog III programming language extends Prolog by redefining the fundamental process at its heart : unification. Into this mechanism, Prolog III integrates refined processing of trees and lists, number processing, and processing of two-valued Boolean algebra. We present the specification of this new language and illustrate its capabilities by means of varied examples. We also present the theoretical foundations of Prolog III, which in fact apply to a whole family of programming languages. The central innovation is to replace the concept of unification by the concept of constraint solving. acmprolog3e.pdf

Une introduction à Prolog III, version française de : An Introduction to Prolog III, dans Communications of the ACM, vol. 33, no. 7, juillet 1990. Résumé. Le langage de programmation Prolog III est une extension de Prolog au niveau de ce qu'il a de plus fondamental, le mécanisme d'unification. Il intègre dans ce mécanisme un traitement plus complet des arbres et des listes, un traitement numérique et un traitement de l'algèbre de Boole à deux valeurs. Nous présentons ici les spécifications de ce nouveau langage et illustrons ses possibilités au moyen d'exemples variés. Nous présentons aussi le modèle théorique de Prolog III qui, en fait, s'applique à toute une famille de langages de programmation. L'idée essentielle est de remplacer la notion d'unification par celle de résolution de contraintes. acmprolog3e.pdf

La naissance de Prolog, avec Philippe Roussel. Brouillon de : The birth of Prolog , dans History of Programming Languages, édité par Thomas J.~Bergin et Richard G.~Gibson, ACM Press/Addison-Wesley, 1996. Résumé. Le langage de programmation Prolog est né d'un projet, dont le but n'était pas de faire un langage de programmation mais de traiter les langages naturels, en l'occurrence le Français. Ce projet a donné naissance à un Prolog préliminaire à la fin 1971 et un Prolog plus définitif à la fin de l'année 1972. Cet article relate l'histoire de ce projet, décrit en détail la version préliminaire de Prolog puis sa version définitive. Les auteurs ont aussi jugé bon de décrire les systèmes-Q un langage qui a joué un rôle important dans la genèse de Prolog. 24juillet92.pdf

Teaching Enseignement

Machines universelles, avril 2002.  Notes de cours de DEUG 2ème année à la Faculté des Sciences de Luminy, Université de la Méditerranée turing.pdf. Enoncés de travaux dirigés et des travaux pratiques : enoncestptd.pdf. Utilitaires pour les travaux pratiques en Maple : turingmapleter.txt , canevasuniverselle.txt , milieuuniverselle.txt, aidetp5.txt. Ce cours constitue la motié d'un cours de 10 fois 2 heures intitulé "Arithmérique et machine de Turing". La partie arithmétique est donnée par Michel Van Caneghem.

Le manuel de Prolog IV. Tutoriel, concepts de base, primitives, Prolog ISO, syntaxe, environnement.
Introduction.pdf,
1-TutorielSurvol.pdf,
2-Bases.pdf,
3-Relations.pdf,
4-PredicatsPredefinis.pdf,
5-PredicatsPredIso,
6-Syntaxe.pdf,
7-SyntaxeIso.pdf,
8-Environment.pdf,
9-EnvGraphique.pdf,
Index.pdf

Curriculum Vitae

Curriculum Vitae, dernière mises à jour, février 1999. Inclut la liste de mes publications. Cvf99a4.ps Cvf99a4.pdf