- Ronald Fagin
Infobox Scientist
name = Ronald Fagin
birth_place = Oklahoma, OK, USA
residence =Los Gatos, California
nationality = American
field =Logic in Computer Science ,Database theory ,Finite model theory ,
Reasoning aboutknowledge
work_institution =IBM Almaden Research Center
alma_mater =Dartmouth College ,University of California, Berkeley
doctoral_advisor =Robert Lawson Vaught
known_for =Fagin's theorem
prizes = Elected toIBM Academy of Technology , Fellow of theAmerican Association for the Advancement of Science , ACM SIGMOD Edgar F. Codd Innovations Award, Fellow ofAssociation for Computing Machinery , Fellow of theIEEE , Seven IBM Outstanding Innovation AwardsRonald Fagin is the Acting Senior Manager of the [http://www.almaden.ibm.com/cs/disciplines/pm/ Mathematics and Related Computer Science group] at
IBM Almaden Research Center . He is best known for his pioneering work indatabase theory ,finite model theory , and reasoning about knowledge [ [http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8240 Reasoning about Knowledge. Co-authors J.Y. Halpern, Y. Moses and M.Y. Vardi. Published by MIT Press, 1995. Paperback edition, 2003.] ] . He is a fellow of the ACM [ [http://fellows.acm.org/fellow_citation.cfm?id=N951889&srt=all ACM Fellowship Citation] ] , and has received numerous other awards [ [http://dimacs.rutgers.edu/Distinguished/Fagin.html Dimacs Speaker Blurb] ] . He is currently chair of the International Conference on Database Theory, to be held inSaint Petersburg ,Russia , in 2009 [ [http://alpha.uhasselt.be/~lucp1080/icdt/ International Conference on Database Theory 2009] ] .Biography
Early life
Ron Fagin was born and grew up in
Oklahoma City . He attendedNorthwest Classen High School . Following that, he completed his undergraduate degree atDartmouth College . Fagin received his Ph.D. in Mathematics from theUniversity of California, Berkeley in 1973, where he worked under the supervision ofRobert Vaught . He joined theIBM Research Division in 1973, spending two years at theThomas J. Watson Research Center , and then transferred in 1975 to what is now theIBM Almaden Research Center inSan Jose, California .Academic contributions
Fagin's theorem , which he proved in his PhD thesis states that existentialsecond-order logic coincides with the complexity classNP in the sense that a decision problem can be expressed in second-order logic if and only if it can be solved by a nondeterministicTuring machine in polynomial time. This work was seminal to the area offinite model theory [Neil Immerman , Descriptive Complexity. Springer-Verlag, 1999] . 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 [Ronald Fagin: Probabilities on Finite Models. Journal of Symbolic Logic, 41(1):50-58, 1976] . This result was proven independently by Glebskiĭ et al. slightly earlier in Russia [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] .He is also known for his work on higher Normal Forms inDatabase Theory , particularly 4NF.ee also
*
Fagin's theorem
*IBM Almaden Research Center References
External links
* [http://www.almaden.ibm.com/cs/people/fagin/ Ronald Fagin's Website at IBM]
* [http://www.almaden.ibm.com/cs/disciplines/pm/ Mathematics and Related Computer Science Group at IBM Almaden Research Center]
Wikimedia Foundation. 2010.
