Ronald Fagin (nacido en 1945) es un matemático e informático estadounidense , y miembro de IBM en el Centro de Investigación IBM Almaden . Es conocido por su trabajo en teoría de bases de datos , teoría de modelos finitos y razonamiento sobre el conocimiento. [1]
Ron Fagin nació y creció en la ciudad de Oklahoma , donde asistió a la escuela secundaria Northwest Classen . Más tarde fue elegido miembro del Salón de la Fama de Northwest Classen. Completó su licenciatura en Dartmouth College . Fagin recibió su doctorado. en Matemáticas de la Universidad de California, Berkeley en 1973, donde trabajó bajo la supervisión de Robert Vaught .
Se unió a la División de Investigación de IBM en 1973, pasó dos años en el Centro de Investigación Thomas J. Watson y luego se transfirió en 1975 a lo que hoy es el Centro de Investigación IBM Almaden en San José, California .
Se ha desempeñado como presidente del comité de programa del Simposio ACM sobre principios de sistemas de bases de datos (1984), Aspectos teóricos del razonamiento sobre el conocimiento (1994), Simposio ACM sobre teoría de la computación (2005) y la Conferencia internacional sobre teoría de bases de datos (2009).
Fagin ha recibido numerosos premios profesionales por su trabajo. Es miembro de la Academia Nacional de Ciencias , la Academia Nacional de Ingeniería y la Academia Estadounidense de Artes y Ciencias . Es miembro de IBM , miembro de ACM , miembro de IEEE , miembro de la Asociación Estadounidense para el Avance de la Ciencia y miembro de la Asociación de Inteligencia Artificial de Asia y el Pacífico. Uno de sus trabajos [2] ganó el Premio Gödel . Recibió un Doctor Honoris Causa de la Universidad de París y una Laurea Honoris Causa de la Universidad de Calabria en Italia. El IEEE le otorgó el premio IEEE W. Wallace McDowell y el premio IEEE Technical Achievement Award [3] (ahora conocido como Edward J. McCluskey Technical Achievement Award [4] ); y la ACM le otorgó el premio ACM SIGMOD Edgar F. Codd Innovations. La Asociación Europea de Informática Teórica (en conjunto con el Grupo de Interés Especial de ACM en Lógica y Computación, la Asociación Europea de Lógica en Informática y la Sociedad Kurt Gödel) le otorgó el él y los coautores de dos de sus artículos, [5] [6] el Premio Alonzo Church de Lógica y Computación . IBM le otorgó ocho premios IBM Outstanding Innovation Awards, dos premios IBM suplementarios de emisión de patentes, otorgados por patentes clave de IBM, tres premios IBM Outstanding Technical Achievement Awards y dos IBM Corporate Awards. Ganó premios al Mejor Trabajo en la Conferencia Internacional Conjunta sobre Inteligencia Artificial de 1985, el Simposio ACM sobre Principios de Sistemas de Bases de Datos de 2001, la Conferencia Internacional sobre Teoría de Bases de Datos de 2010 y la Conferencia Internacional sobre Teoría de Bases de Datos de 2015. Ganó premios Test-of-Time de 10 años en el Simposio ACM sobre principios de sistemas de bases de datos de 2011, la Conferencia internacional sobre teoría de bases de datos de 2013 y el Simposio ACM sobre principios de sistemas de bases de datos de 2014.
El teorema de Fagin , que demostró en su tesis doctoral, establece que la lógica existencial de segundo orden coincide con la clase de complejidad NP en el sentido de que un problema de decisión puede expresarse en lógica existencial de segundo orden si y sólo si puede resolverse mediante un Máquina de Turing no determinista en tiempo polinómico. Este trabajo ayudó a fundar el área de la teoría de modelos finitos . [7] [8]
Otro resultado que demostró en su tesis doctoral es que la lógica de primer orden tiene una ley cero-uno, que dice que si S es una oración de primer orden con solo símbolos relacionales (sin funciones o símbolos constantes), entonces la fracción de n Las estructuras de nodos que satisfacen S convergen cuando n tiende al infinito y, de hecho, convergen a 0 o 1. [9] Este resultado fue demostrado independientemente por Glebskiĭ y sus coautores anteriormente (1969) en Rusia, [10] con una perspectiva muy diferente. prueba.
También es conocido por su trabajo sobre formas normales superiores en teoría de bases de datos , particularmente 4NF , 5NF y DK/NF .
Además del teorema de Fagin, otros conceptos que llevan el nombre de Fagin son el "algoritmo de Fagin" para la agregación de puntuaciones, [11] el "inverso de Fagin" para el intercambio de datos, [12] y los "juegos de Fagin" [13] y los "juegos de Ajtai-Fagin" [ 14] para demostrar que la inexpresabilidad resulta en lógica.
Fagin es autor o coautor de numerosos artículos [15] [16] y un libro:
Artículos, una selección: