Accueil🇫🇷Chercher

Ronald Fagin

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.

Ronald Fagin
Description de cette image, également commentée ci-après
Ronald Fagin
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

Biographie

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].

Prix et distinctions

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.

  • Il est laurĂ©at du Prix Gödel en 2014 et docteur honoris causa de l'UniversitĂ© de Paris ;
  • l'IEEE lui a dĂ©cernĂ© le prix W. Wallace McDowell (en) et le IEEE Technical Achievement Award[8] ;
  • l'ACM lui a attribuĂ© le ACM SIGMOD Edgar F. Codd Innovations Award[9] ;
  • IBM lui a dĂ©cernĂ© de nombreuses rĂ©compenses :
    • huit rĂ©compenses pour des innovations exceptionnelles (IBM Outstanding Innovation Award),
    • deux rĂ©compenses supplĂ©mentaires pour des dĂ©pĂ´ts de brevets (IBM supplemental Patent Issue Award), accordĂ©s pour des brevets clĂ© d'IBM,
    • la rĂ©compense IBM pour des accomplissements exceptionnelles (IBM Outstanding Technical Achievement Award)
    • et le prix de l'entreprise IBM (IBM Corporate Award).
  • Fagin figure sur la liste des « chercheurs frĂ©quemment citĂ©s » (Highly Cited Researchers)[10].
  • Il a reçu le prix du meilleur article en 1985 Ă  la International Joint Conference on Artificial Intelligence, Ă  la confĂ©rence ACM Symposium on Principles of Database Systems en 2001, et Ă  la confĂ©rence International Conference on Database Theory en 2003.
  • Il a obtenu le prix Test-of-Time de dix ans aux confĂ©rences ACM Symposium on Principles of Database Systems de 2011, International Conference on Database Theory de 2013 et ACM Symposium on Principles of Database Systems de 2014.

Travaux

Le théorème de Fagin

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].

Autres contributions

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).

Publications

Fagin est auteur et coauteur de nombreuses publications dans son domaine d'expertise[14] - [15]. Il est notamment coauteur du livre :

  • Ronald Fagin, Joseph Y. Halpern, Yoram Moses et Moshe Vardi, Reasoning about Knowledge, MIT Press, (1re Ă©d. 1995), 517 p. (ISBN 978-0-262-56200-3, lire en ligne)

et auteur ou coauteur des articles :

Notes et références
  1. American Men and Women of Science, Thomson Gale, 2004.
  2. Ronald Fagin, Joseph Y. Halpern, Yoram Moses et Moshe Vardi, Reasoning about Knowledge, MIT Press, (1re Ă©d. 1995), 517 p. (ISBN 978-0-262-56200-3, lire en ligne).
  3. mitpress.mit.edu
  4. ACM Symposium on Principles of Database Systems 1984
  5. Theoretical Aspects of Reasoning about Knowledge 1994
  6. Symposium on Theory of Computing 2005
  7. International Conference on Database Theory 2009
  8. IEEE Technical Achievement Award
  9. ACM SIGMOD Edgar F. Codd Innovations Award
  10. Institute for Scientific Information Highly Cited Researchers.
  11. (en) Neil Immerman, Descriptive Complexity, New York, Springer-Verlag, , 268 p. (ISBN 0-387-98600-6, lire en ligne), p. 113-119.
  12. Ronald Fagin, « Probabilities on Finite Models », Journal of Symbolic Logic, vol. 41, no 1,‎ , p. 50-58.
  13. Y. V. Glebskiĭ, D.I. Kogan, M.I. Liogonkiĭ et V.A. Talanov, « Range and degree of realizability of formulas in the restricted predicate calculu », Kibernetika, vol. 2,‎ , p. 17-28.
  14. Ronald Fagin: IBM Almaden Research Center Profil Google Scholar
  15. Ronald Fagin sur le site de bibliographie DBLP
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ronal Fagin » (voir la liste des auteurs).

Articles connexes

Liens externes
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.