Ronald Fagin

from Wikipedia, the free encyclopedia
Ronald Fagin

Ronald Fagin (born May 1, 1945 in Oklahoma City ) is an American computer scientist .

Life

Fagin studied at Dartmouth College and received his PhD in 1973 from the University of California, Berkeley , with Robert Vaught . He then went into research at IBM , first at the Thomas J. Watson Research Center and from 1975 at the IBM Almaden Research Center in San José ( California ). There he is in the group on Foundations of Computer Science .

plant

In 1973 he proved in his thesis the set of Fagin the descriptive complexity theory and finite model theory .

He is known for fundamental results in the theory of databases , for example his widely accepted definition of the fourth normal form in the theory of relational databases , his theory of acyclic database systems or work on inaccurate ( fuzzy ) queries of databases (see for example Top-N query ). He is one of the inventors of extendible hashing .

He is also known for a basic probabilistic outcome on logic. In 1976 he proved that predicate logic over finite structures satisfies a 0–1 law ( zero one law ), independently proven by Y. Glebsky and his students D. Kogan, M. Liogonki, and V. Talanov in 1969 in the Soviet Union. This was the first 0-1 sentence in the logic.

In 2012 Fagin received the W. Wallace McDowell Award and in 2004 the ACM SIGMOD Edgar F. Codd Innovation Award. He is an IBM Fellow and a member of the IBM Academy of Technology and has received eight IBM Outstanding Innovation Awards, the IBM Outstanding Technical Achievement Award, the IBM Corporate Award and two IBM Awards for Patents. In 1985 he received the Best Paper Award from the International Joint Conference on Artificial Intelligence, in 2001 the Best Paper Award from the ACM Symposium on Principles of Database Systems and in 2010 the Best Paper Award from the International Conference on Database Theory. He is also an IEEE Fellow, ACM Fellow and a member of the American Association for the Advancement of Science . He is an honorary doctor from the University of Paris . For 2014, together with Moni Naor and Amnon Lotem, he was awarded the Gödel Prize by ACM and EATCS for their work Optimal Aggregation Algorithms for Middleware , which introduced the threshold algorithm and instance optimality . He was also admitted to the American Academy of Arts and Sciences in 2014 and to the National Academy of Sciences in 2020 .

Fonts

  • with JY Halpern, Y. Moses, Moshe Y. Vardi : Reasoning about Knowledge , MIT Press 1995, 2003.

Web links

Individual evidence

  1. ↑ Life and career data according to American Men and Women of Science , Thomson Gale 2004
  2. ↑ Fagin Probabilities on Finite Models , Journal of Symbolic Logic, Volume 41, 1976, pp. 50-58.
  3. ↑ That is, sentences formed with predicate logic about a set of structures D apply to almost all or almost none of the structures, asymptotically with probability 1 or 0.
  4. ↑ Kibernetika, Volume 2, 1969, pp. 31-42.
  5. ^ Codd Award
  6. ↑ J. Comput. Syst. Sci., Vol. 66, 2003, pp. 614-656
personal data
SURNAME Fagin, Ronald
BRIEF DESCRIPTION American computer scientist
DATE OF BIRTH May 1, 1945
PLACE OF BIRTH Oklahoma City