Loading AI tools
informaticien américain De Wikipédia, l'encyclopédie libre
Ronald Fagin (né en 1945) est un informaticien américain, Fellow IBM au IBM Almaden Research Center. Il est réputé pour ses travaux pionniers en complexité descriptive, logique mathématique, théorie des bases de données, théorie des modèles finis, et le raisonnement sur la connaissance[2],[3]. Il est un des lauréats du Prix Gödel 2014.
Naissance |
[1] Oklahoma City (Oklahoma, États-Unis) |
---|---|
Nationalité | Américain |
Résidence | Los Gatos, Californie |
Domaines |
Complexité descriptive, Théorie des bases de données, Théorie des modèles finis, Rang et agrégation de scores, Raisonnement sur la connaissance |
---|---|
Institutions | Centre de recherche IBM à Almaden |
Formation |
Dartmouth College, Université de Californie à Berkeley |
Directeur de thèse | Robert Lawson Vaught |
Renommé pour | Théorème de Fagin |
Distinctions | Prix Gödel 2014 |
Ron Fagin est né et a grandi à Oklahoma City, où il est élève à la Northwest Classen High School (en). Il continue par des études de premier cycle universitaire au Dartmouth College. Il obtient un Ph. D. en mathématiques en 1973, à l'université de Californie à Berkeley, sous la direction de Robert L. Vaught.
Il rejoint le département IBM Research en 1973, et passe deux années au Thomas J. Watson Research Center, puis il migre vers ce qui est connu maintenant sous le nom de IBM Almaden Research Center situé à San José, en Californie.
Il a été président du comité de programme du ACM Symposium on Principles of Database Systems en 1984[4], de la conférence Theoretical Aspects of Reasoning about Knowledge en 1994[5], du ACM Symposium on Theory of Computing en 2005[6], et de la International Conference on Database Theory en 2009[7].
Fagin a reçu de nombreuses distinctions pour ses travaux. Il est membre élu de la Académie nationale d'ingénierie des États-Unis et de l'Académie américaine des arts et des sciences, il est Fellow d'IBM, Fellow de l'ACM, de l'IEEE, et Fellow de l'Association américaine pour l'avancement des sciences.
Le théorème de Fagin, qu'il a prouvé dans sa thèse de doctorat, affirme que la logique du second ordre existentielle coïncide avec la classe de complexité NP en ce sens qu'un problème peut être exprimé en logique du second ordre existentielle si et seulement s'il peut être résolu par une machine de Turing non déterministe en temps polynomial. Ce théorème était pionnier dans le domaine de la théorie des modèles finis et de la complexité descriptive[11].
Un autre résultat célèbre que Fagin a démontré est que la logique du premier ordre possède une loi zéro-un, un outil pour démontrer des résultats d'inexpressibilité dans des langages de requêtes de bases de données[12]. Ce résultat a été prouvé indépendamment, plusieurs années auparavant, par Glebskiĭ et d'autres en URSS[13].
Il est aussi connu pour son travail sur des formes normales d'ordre supérieur dans la théorie des bases de données, en particulier la quatrième forme normale (4NF).
Fagin est auteur et coauteur de nombreuses publications dans son domaine d'expertise[14],[15]. Il est notamment coauteur du livre :
et auteur ou coauteur des articles :
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.