Ronald Fagin

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

Ronald Fagin
Ronald Fagin
Born1945[1]
Oklahoma City, OK, USA
NationalityAmerican
Alma materDartmouth College,
University of California, Berkeley
Known forFagin's theorem
AwardsGödel prize (2014),
W. Wallace McDowell Award (2012),
SIGMOD Edgar F. Codd Innovations Award (2004)
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

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 is a Member of the National Academy of Sciences, National Academy of Engineering, and American Academy of Arts and Sciences. He is an IBM Fellow, ACM Fellow, IEEE Fellow, and Fellow of the American Association for the Advancement of Science. One of his papers [7] won the Gödel Prize. He received a Docteur Honoris Causa from the University of Paris, and a Laurea Honoris Causa from the University of Calabria in Italy. The IEEE granted him the IEEE W. Wallace McDowell Award and the IEEE Technical Achievement Award [8] (now known as the Edward J. McCluskey Technical Achievement Award [9]); and the ACM granted him the ACM SIGMOD Edgar F. Codd Innovations Award[10]. The European Association for Theoretical Computer Science (in conjunction with the ACM Special Interest Group for Logic and Computation, the European Association for Computer Science Logic, and the Kurt Gödel Society) granted him and the co-authors of two of his papers [11], [12] the Alonzo Church Award the Alonzo Church Award for Logic and Computation [13]. IBM granted him eight IBM Outstanding Innovation Awards, two IBM supplemental Patent Issue Awards, given for key IBM patents, three IBM Outstanding Technical Achievement Awards, and two IBM Corporate Awards. He won Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, the 2010 International Conference on Database Theory, and the 2015 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 non-deterministic Turing machine in polynomial time. This work helped found the area of finite model theory.[14] [15]

Other contributions

Another result that he proved in his PhD thesis is that first-order logic has a zero-one law, a tool for proving inexpressibility results for database query languages.[16] This result was proved independently by Glebskiĭ et al. earlier (1969) in Russia,[17] with a very different proof.

He is also known for his work on higher normal forms in database theory, particularly 4NF, 5NF and DK/NF.

Besides Fagin's Theorem, other concepts named after Fagin are "Fagin's algorithm" for score aggregation,[18] the "Fagin-inverse" for data exchange,[19] and "Fagin games" [20] and "Ajtai Fagin games" [21] for proving inexpressibility results in logic.

Publications

Fagin has authored or co-authored numerous articles,[22][23] and a book:

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

Articles, a selection:

gollark: I'm not actually on. You will need to wait.
gollark: PotatOS installation without permission is against the rules, you can put stuff in my claims safely...
gollark: It's like people distrust me or something.
gollark: What does the hexahedron have to do with potatOS?
gollark: And?

References
  1. American Men and Women of Science, Thomson Gale, 2004.
  2. Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi, Reasoning about Knowledge, 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. Ronald Fagin, Amnon Lotem, and Moni Naor., "Optimal aggregation algorithms for middleware". Journal of Computer and System Sciences 66 (2003): 614-656. Extended abstract appeared in Proc. 2001 ACM Symposium on Principles of Database Systems, pp. 102-113.
  8. IEEE Computer Society Names 2011 Technical Achievement Winners
  9. The Edward J. McCluskey Technical Achievement Award
  10. ACM SIGMOD Edgar F. Codd Innovations Award
  11. Ronald Fagin, Phokion Kolaitis, Renee J Miller, and Lucian Popa, “Data exchange: semantics and query answering”, Theoretical Computer Science 336 (2005): 89-124. (Special issue for selected papers from the 2003 International Conference on Database Theory).
  12. Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan, “Composing schema mappings: Second-order dependencies to the rescue”, ACM Trans. on Database Systems 30, 4 (Dec. 2005), pp. 994-1055. (Special issue for selected papers from the 2004 ACM SIGMOD/PODS Conference).
  13. The 2020 Alonzo Church Award
  14. Neil Immerman, Descriptive Complexity. Springer-Verlag, 1999.
  15. Leonid Libkin, Elements of Finite Model Theory. Springer 2004. ISBN 978-3-540-21202-7.
  16. Ronald Fagin: "Probabilities on Finite Models". Journal of Symbolic Logic, 41(1):50-58, 1976
  17. 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
  18. Ronald Fagin. "Combining fuzzy information from multiple systems." Journal of Computer and System Sciences 58 (1999): 83-99. (Special issue for selected papers from the 1996 ACM Symposium on Principles of Database Systems).
  19. Ronald Fagin, "Inverting schema mappings". ACM Trans. on Database Systems 32, 4, Nov. 2007. (Special issue for selected papers from the 2006 ACM Symposium on Principles of Database Systems.)
  20. Ronald Fagin, "Monadic generalized spectra". Zeitschr. f. math. Logik und Grundlagen d. Math. 21, 1975, pp. 89-96.
  21. Miklos Ajtai and Ronald Fagin, "Reachability is harder for directed than for undirected finite graphs". Journal of Symbolic Logic 55, 1, March 1990, pp. 113-150. Preliminary version appeared in Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 358-367.
  22. Ronald Fagin: IBM Almaden Research Center Google Scholar profile
  23. Ronald Fagin The DBLP Computer Science Bibliography
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.