Ronald Fagin
Wikipedia on Answers.com:
Top
Ronald Fagin
| Ronald Fagin | |
|---|---|
 Ronald Fagin |
|
| Born | May 1, 1945 Oklahoma City, OK, USA |
| Residence | Los Gatos, California |
| Nationality | American |
| Fields | Logic in Computer Science, Database theory, Finite model theory, Reasoning about knowledge |
| Institutions | IBM Almaden Research Center |
| Alma mater | Dartmouth College, University of California, Berkeley |
| Doctoral advisor | Robert Lawson Vaught |
| Known for | Fagin's theorem |
| Notable awards |
|
Ronald Fagin is an 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.[1] He has received numerous professional awards for his work (see list on right).
|
Contents
|
Biography
Early life
Ron Fagin was born on May 1, 1945 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.
Academic contributions
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.[2] 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.[3] This result was proven independently by Glebskiĭ et al. slightly earlier in Russia.[4] He is also known for his work on higher Normal Forms in Database Theory, particularly 4NF.
He has served as program committee chair for ACM Symposium on Principles of Database Systems 1984,[5] Theoretical Aspects of Reasoning about Knowledge 1994,[6] ACM Symposium on Theory of Computing 2005,[7] and the International Conference on Database Theory 2009.[8]
See also
References
- ^ Reasoning about Knowledge. Co-authors J.Y. Halpern, Y. Moses and M.Y. Vardi. Published by MIT Press, 1995. Paperback edition, 2003.
- ^ Neil Immerman, Descriptive Complexity. Springer-Verlag, 1999
- ^ Ronald Fagin: Probabilities on Finite Models. Journal of Symbolic Logic, 41(1):50-58, 1976
- ^ 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
- ^ ACM Symposium on Principles of Database Systems 1984
- ^ Theoretical Aspects of Reasoning about Knowledge 1994
- ^ Symposium on Theory of Computing 2005
- ^ International Conference on Database Theory 2009
External links
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
Post a question - any question - to the WikiAnswers community:
Copyrights:
Wikipedia on Answers.com
This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article Ronald Fagin.
Read more