stringtranslate.com

Ronald Fagin

Ronald Fagin (nacido en 1945) es un matemático y científico informático estadounidense , e IBM Fellow en el IBM Almaden Research Center . 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 Oklahoma City , 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, pasando dos años en el Centro de Investigación Thomas J. Watson , y luego se trasladó 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 de 1984, Aspectos Teóricos del Razonamiento sobre el Conocimiento de 1994, Simposio ACM sobre Teoría de la Computación de 2005 y la Conferencia Internacional sobre Teoría de Bases de Datos de 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 , ACM , IEEE , de la Asociación Estadounidense para el Avance de la Ciencia y de la Asociación de Inteligencia Artificial de Asia y el Pacífico. Uno de sus artículos [2] ganó el Premio Gödel . Recibió un Docteur Honoris Causa de la Universidad de París y un Laurea Honoris Causa de la Universidad de Calabria en Italia. El IEEE le otorgó el Premio IEEE W. Wallace McDowell y el Premio al Logro Técnico IEEE [3] (ahora conocido como el Premio al Logro Técnico Edward J. McCluskey [4] ); y la ACM le otorgó el Premio ACM SIGMOD Edgar F. Codd Innovations Award La Asociación Europea de Ciencias de la Computación Teórica (en conjunto con el Grupo de Interés Especial de la ACM para Lógica y Computación, la Asociación Europea de Lógica de Ciencias de la Computación y la Sociedad Kurt Gödel) le otorgó a él y a los coautores de dos de sus artículos, [5] [6] el Premio Alonzo Church para Lógica y Computación . IBM le otorgó ocho Premios IBM a la Innovación Sobresaliente, dos Premios IBM complementarios a la Emisión de Patentes, otorgados por patentes clave de IBM, tres Premios IBM a los Logros Técnicos Sobresalientes y dos Premios Corporativos IBM. Ganó premios al Mejor Artículo en la Conferencia Conjunta Internacional sobre Inteligencia Artificial de 1985, el Simposio ACM de 2001 sobre Principios de Sistemas de Bases de Datos, la Conferencia Internacional de Teoría de Bases de Datos de 2010 y la Conferencia Internacional de 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 solo si puede resolverse mediante una máquina de Turing no determinista en tiempo polinomial. 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 símbolos de función o constantes), entonces la fracción de estructuras de n nodos que satisfacen S converge cuando n tiende a infinito, y de hecho converge a 0 o 1. [9] Este resultado fue demostrado independientemente por Glebskiĭ y coautores anteriormente (1969) en Rusia, [10] con una prueba muy diferente.

También es conocido por su trabajo en formas normales superiores en la teoría de bases de datos , particularmente 4NF , 5NF y DK/NF .

Además del teorema de Fagin, otros conceptos que llevan este nombre son el "algoritmo de Fagin" para la agregación de puntuaciones, [11] el "Fagin-inverso" para el intercambio de datos, [12] y los "juegos de Fagin" [13] y los "juegos de Ajtai-Fagin" [14] para demostrar resultados de inexpresabilidad 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". Journal of Computer and System Sciences 66 (2003): 614-656. El resumen ampliado apareció en Proc. 2001 ACM Symposium on Principles of Database Systems, págs. 102-113.
  3. ^ La IEEE Computer Society nombra a los ganadores técnicos de 2011
  4. ^ Premio al Logro Técnico 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 asignaciones de esquemas: dependencias de segundo orden al rescate”, ACM Trans. on Database Systems 30, 4 (diciembre de 2005), págs. 994-1055. (Número especial para artículos seleccionados de la Conferencia ACM SIGMOD/PODS de 2004).
  7. ^ Neil Immerman , Complejidad descriptiva . Springer-Verlag, 1999.
  8. ^ Leonid Libkin , Elementos de la teoría de modelos finitos. Springer 2004. ISBN  978-3-540-21202-7 .
  9. ^ Ronald Fagin: "Probabilidades en modelos finitos". Journal of Symbolic Logic, 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. "Combinación de información difusa de múltiples sistemas". Journal of Computer and System Sciences 58 (1999): 83-99. (Número especial para artículos seleccionados del Simposio ACM de 1996 sobre Principios de Sistemas de Bases de Datos).
  12. ^ Ronald Fagin, "Inversión de asignaciones de esquemas". ACM Trans. on Database Systems 32, 4, noviembre de 2007. (Número especial con 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 grafos 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. 29th IEEE Symposium on Foundations of Computer Science, 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