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 the Manager of the Foundations of Computer Science group 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 |
[edit] Biography
[edit] 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.
[edit] 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]
[edit] See also
[edit] 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
[edit] External links
- American computer scientists
- Database researchers
- Fellows of the Association for Computing Machinery
- Fellow Members of the IEEE
- Fellows of the American Association for the Advancement of Science
- SIGMOD Edgar F. Codd Innovations Award winners
- Living people
- 1945 births
- People from Oklahoma City, Oklahoma
- Northwest Classen High School alumni
- Dartmouth College alumni
- University of California, Berkeley alumni
- IBM employees
