stringtranslate.com

Ronald Fagin

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]

Biografía

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.

Trabajar

teorema de fagin

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]

Otras contribuciones

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.

Publicaciones

Fagin es autor o coautor de numerosos artículos [15] [16] y un libro:

Artículos, una selección:

Referencias

  1. ^ Ronald Fagin, Joseph Y. Halpern, Yoram Moses y Moshe Y. Vardi, Reasoning about Knowledge, MIT Press, 1995. Edición de bolsillo, 2003.
  2. ^ Ronald Fagin, Amnon Lotem y Moni Naor., "Algoritmos de agregación óptimos para middleware". Revista de Ciencias de la Computación y Sistemas 66 (2003): 614-656. El resumen ampliado apareció en Proc. Simposio ACM de 2001 sobre principios de sistemas de bases de datos, págs.
  3. ^ IEEE Computer Society nombra a los ganadores técnicos de 2011
  4. ^ Premio a los logros técnicos Edward J. McCluskey
  5. ^ Ronald Fagin, Phokion Kolaitis, Renee J Miller y Lucian Popa, "Intercambio de datos: semántica y respuesta a consultas", Theoretical Computer Science 336 (2005): 89-124. (Número especial para artículos seleccionados de la Conferencia Internacional sobre Teoría de Bases de Datos de 2003).
  6. ^ Ronald Fagin, Phokion G. Kolaitis, Lucian Popa y Wang-Chiew Tan, “Composición de mapeos de esquemas: dependencias de segundo orden para el rescate”, ACM Trans. sobre sistemas de bases de datos 30, 4 (diciembre de 2005), págs. 994-1055. (Número especial para artículos seleccionados de la Conferencia ACM SIGMOD/PODS 2004).
  7. ^ Neil Immerman , Complejidad descriptiva . Springer-Verlag, 1999.
  8. ^ Leonid Libkin , Elementos de la teoría de modelos finitos. Saltador 2004. ISBN  978-3-540-21202-7 .
  9. ^ Ronald Fagin: "Probabilidades en modelos finitos". Revista de lógica simbólica, 41(1):50-58, 1976
  10. ^ Glebskiĭ, YV; Kogan, DI; Liogonkiĭ, MI; Talanov, VA (1969). "Rango y grado de realizabilidad de fórmulas en el cálculo de predicados restringidos". Kibernética . 5 (2): 17–28. doi :10.1007/bf01071084. S2CID  121409759.
  11. ^ Ronald Fagin. "Combinando información difusa de múltiples sistemas". Revista de Ciencias de la Computación y Sistemas 58 (1999): 83-99. (Número especial para artículos seleccionados del Simposio ACM sobre principios de sistemas de bases de datos de 1996).
  12. ^ Ronald Fagin, "Invertir asignaciones de esquemas". Transmisión ACM. on Database Systems 32, 4, noviembre de 2007. (Número especial para artículos seleccionados del Simposio ACM de 2006 sobre principios de sistemas de bases de datos).
  13. ^ Ronald Fagin, "Espectros monádicos generalizados". Zeitschr. F. matemáticas. Logik und Grundlagen d. Matemáticas. 21, 1975, págs. 89-96.
  14. ^ Miklos Ajtai y Ronald Fagin, "La accesibilidad es más difícil para los gráficos finitos dirigidos que para los no dirigidos". Journal of Symbolic Logic 55, 1, marzo de 1990, págs. 113-150. La versión preliminar apareció en Proc. 29º Simposio del IEEE sobre fundamentos de la informática, 1988, págs. 358-367.
  15. ^ Publicaciones de Ronald Fagin indexadas por Google Scholar
  16. ^ Ronald Fagin en el servidor de bibliografía DBLP

enlaces externos