Ronald Fagin

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 about knowledge
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 to IBM Academy of Technology, Fellow of the American Association for the Advancement of Science, ACM SIGMOD Edgar F. Codd Innovations Award, Fellow of Association for Computing Machinery, Fellow of the IEEE, Seven IBM Outstanding Innovation Awards

Ronald 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 in database 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 in Saint 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 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 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 [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 in Database 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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Fagin's theorem — is a result in descriptive complexity theory which states that the set of all properties expressible in existential second order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP which… …   Wikipedia

  • Fagin — steht für: einen schwach giftigen Inhaltsstoff in Bucheckern, siehe Trimethylamin Joe Fagin (* 1940), britischer Popsänger Ronald Fagin (* 1945), amerikanischer Informatiker Fagin (Charles Dickens), einen fiktiven Charakter in Charles Dickens… …   Deutsch Wikipedia

  • Théorème de Fagin — Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l égalité de la classe NP (en) et de la classe des problèmes exprimables en logique du second ordre existentielle, c est à dire en logique du premier… …   Wikipédia en Français

  • Satz von Fagin — Der Satz von Fagin ist ein 1973 von Ronald Fagin bewiesener Satz aus der deskriptiven Komplexitätstheorie, der aussagt, dass die Menge aller mit Hilfe der existentiellen Prädikatenlogik zweiter Stufe beschreibbaren Sätze genau die… …   Deutsch Wikipedia

  • Database normalization — In the design of a relational database management system (RDBMS), the process of organizing data to minimize redundancy is called normalization. The goal of database normalization is to decompose relations with anomalies in order to produce… …   Wikipedia

  • Fourth normal form — (4NF) is a normal form used in database normalization. Introduced by Ronald Fagin in 1977, 4NF is the next level of normalization after Boyce Codd normal form (BCNF). Whereas the second, third, and Boyce Codd normal forms are concerned with… …   Wikipedia

  • Beschreibende Komplexitätstheorie — Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP… …   Deutsch Wikipedia

  • Deskriptive Komplexität — Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP… …   Deutsch Wikipedia

  • Deskriptive Komplexitätstheorie — Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP… …   Deutsch Wikipedia

  • Descriptive complexity theory — For other uses, see Kolmogorov complexity. Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”