Jump to content

Ronald Fagin

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Bender235 (talk | contribs) at 08:48, 20 May 2014. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Ronald Fagin
Ronald Fagin
Born1945[1]
Oklahoma City, OK, USA
NationalityAmerican
Alma materDartmouth College,
University of California, Berkeley
Known forFagin's theorem
Scientific career
FieldsLogic in Computer Science,
Database theory,
Finite model theory,
Rank and score aggregation,
Reasoning about knowledge
InstitutionsIBM Almaden Research Center
Doctoral advisorRobert Lawson Vaught

Ronald Fagin (born 1945) is an American computer scientist and IBM Fellow at the IBM Almaden Research Center. He is best known for his pioneering work in database theory, finite model theory, and reasoning about knowledge.[2]

Biography

Ron Fagin was born and grew up in Oklahoma City, where he attended Northwest Classen High School. Following that, he completed his undergraduate degree at Dartmouth College. Fagin received his Ph.D. in Mathematics from the University of California, Berkeley in 1973, where he worked under the supervision of Robert Vaught.

He joined the IBM Research Division in 1973, spending two years at the Thomas J. Watson Research Center, and then transferred in 1975 to what is now the IBM Almaden Research Center in San Jose, California.

He has served as program committee chair for ACM Symposium on Principles of Database Systems 1984,[3] Theoretical Aspects of Reasoning about Knowledge 1994,[4] ACM Symposium on Theory of Computing 2005,[5] and the International Conference on Database Theory 2009.[6]

Fagin has received numerous professional awards for his work. He was elected Member of the National Academy of Engineering, American Academy of Arts and Sciences, IBM Fellow, ACM Fellow, IEEE Fellow, and Fellow of the American Association for the Advancement of Science. He won the 2014 Gödel Prize and he received a Docteur Honoris Causa from the University of Paris. The IEEE granted him the IEEE W. Wallace McDowell Award and the IEEE Technical Achievement Award;[7] the ACM the ACM SIGMOD Edgar F. Codd Innovations Award[8] and IBM Eight IBM Outstanding Innovation Awards, Two IBM supplemental Patent Issue Awards, given for key IBM patents, the IBM Outstanding Technical Achievement Award, and the IBM Corporate Award. Fagin is listed among the "Highly Cited Researchers."[9] He won Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, and the 2010 International Conference on Database Theory. He won 10-year Test-of-Time Awards at the 2011 ACM Symposium on Principles of Database Systems, the 2013 International Conference on Database Theory, and the 2014 ACM Symposium on Principles of Database Systems.

Work

Fagin's theorem

Fagin's theorem, which he proved in his PhD thesis, states that existential second-order logic coincides with the complexity class NP in the sense that a decision problem can be expressed in existential second-order logic if and only if it can be solved by a nondeterministic Turing machine in polynomial time. This work was seminal to the area of finite model theory.[10]

Other contributions

Another famous result that he proved is that first-order logic has a zero-one law, a tool for proving inexpressibility results for database query languages.[11] This result was proven independently by Glebskiĭ et al. slightly earlier in Russia.[12]

He is also known for his work on higher Normal Forms in Database Theory, particularly 4NF.

Publications

Fagin has authored and co-authored many publications in his fields of expertise.[13][14] Books, a selection:

  • Fagin, Ronald, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Reasoning about knowledge. MIT press (1995). Paperback edition (2003).

Articles, a selection:

References

  1. ^ American Men and Women of Science, Thomson Gale, 2004.
  2. ^ Reasoning about Knowledge. Co-authors J.Y. Halpern, Y. Moses and M.Y. Vardi. Published by MIT Press, 1995. Paperback edition, 2003.
  3. ^ ACM Symposium on Principles of Database Systems 1984
  4. ^ Theoretical Aspects of Reasoning about Knowledge 1994
  5. ^ Symposium on Theory of Computing 2005
  6. ^ International Conference on Database Theory 2009
  7. ^ IEEE Technical Achievement Award
  8. ^ ACM SIGMOD Edgar F. Codd Innovations Award
  9. ^ Institute for Scientific Information Highly Cited Researchers
  10. ^ Neil Immerman, Descriptive Complexity. Springer-Verlag, 1999
  11. ^ Ronald Fagin: Probabilities on Finite Models. Journal of Symbolic Logic, 41(1):50-58, 1976
  12. ^ Y.V. Glebskiĭ, D.I. Kogan, M.I. Liogonkiĭ, and V.A. Talanov: Range and degree of realizability of formulas in the restricted predicate calculus. Kibernetika, 2:17-28, 1969
  13. ^ Ronald Fagin: IBM Almaden Research Center Google Scholar profile
  14. ^ Ronald Fagin The DBLP Computer Science Bibliography

External links

Template:Persondata

Retrieved from "https://en.wikipedia.org/w/index.php?title=Ronald_Fagin&oldid=609356628"