Ronald Fagin

Ronald Fagin
Ronald Fagin, IBM Researcher.jpg
Ronald Fagin
Geboren 1945
Oklahoma City, OK, UNS.
Staatsangehörigkeit amerikanisch
Alma Mater Dartmouth College,
Universität von Kalifornien, Berkeley
Bekannt für Fagins Theorem
Auszeichnungen Gödel -Preis (2014),
W. Wallace McDowell Award (2012),
Sigmod Edgar F. Codd Innovations Award (2004)
Wissenschaftliche Karriere
Felder Logik in der Informatik,
Datenbanktheorie,
Finite -Modell -Theorie,
Rang- und Bewertungsaggregation,
Argumentation über Wissen
Institutionen IBM Almaden Research Center
Doktorand Robert Lawson Vaught

Ronald Fagin (geboren 1945) ist ein Amerikaner Mathematiker und Informatiker, und IBM Fellow Bei der IBM Almaden Research Center. Er ist bekannt für seine Arbeit in Datenbanktheorie, Finite -Modell -Theorieund Denken über Wissen.[1]

Biografie

Ron Fagin wurde geboren und wuchs in auf Oklahoma City, wo er besuchte Northwest Classen High School. Er wurde später in die Northwest Clasden Hall of Fame gewählt. Er absolvierte seinen Bachelor -Abschluss bei Dartmouth College. Fagin erhielt seine Ph.D. in Mathematik von der Universität von Kalifornien, Berkeley 1973 arbeitete er unter der Aufsicht von Robert Vaught.

Er schloss sich dem an IBM -Forschung Division im Jahr 1973, zwei Jahre am Thomas J. Watson Research Centerund dann 1975 auf das, was jetzt ist, übertragen IBM Almaden Research Center in San Jose, Kalifornien.

Er war Vorsitzender des Programmausschusses für das ACM -Symposium für Prinzipien von Datenbanksystemen 1984, ACM -Symposium über Prinzipien von Datenbanksystemen 1984, Theoretische Aspekte des Denkens über Wissen 1994, Theoretische Aspekte des Denkens über Wissen 1994, ACM -Symposium über Theorie der Berechnung von 2005, Symposium on Theory of Computing 2005 und die Internationale Konferenz zur Datenbanktheorie 2009.

Fagin hat zahlreiche professionelle Auszeichnungen für seine Arbeit erhalten. Er ist Mitglied der Nationale Akademie der Wissenschaften, Nationale Akademie des Ingenieurwesens, und Amerikanische Akademie für Kunst und Wissenschaften. Er ist ein IBM Fellow, ACM Fellow, IEEE Stipendiat und Fellow der American Association for the Advancement of Science. Eines seiner Papiere [2] gewann das Gödel -Preis. Er erhielt einen Docteur Honoris Causa von der Universität von Parisund ein Laurea ehren Universität Kalabrien in Italien. Der IEEE gewährte ihm das IEEE W. Wallace McDowell Award und den IEEE Technical Achievement Award [3] (Jetzt bekannt als Edward J. McCluskey Technical Achievement Award [4]); und die ACM gewährte ihm den ACM Sigmod Edgar F. Codd Innovations Award.[5] Die Europäische Vereinigung für theoretische Informatik (in Verbindung mit der ACM Special Interest Group für Logik und Berechnung, der Europäischen Vereinigung für Informatik-Logik und der Kurt Gödel Society) gewährte ihm und den Mitautoren zweier seiner Zeitungen.[6][7] Der Alonzo Church Award für Logik und Berechnung. IBM gewährte ihm acht IBM Outstanding Innovation Awards, zwei IBM Supplemental Patent Issue Awards, die für wichtige IBM -Patente, drei IBM Outstanding Technical Achievement Awards und zwei IBM Corporate Awards vergeben. Er gewann die Best Paper Awards auf der Internationalen gemeinsamen Konferenz über künstliche Intelligenz von 1985, das ACM -Symposium 2001 über Prinzipien von Datenbanksystemen, die Internationale Konferenz für Datenbanktheorie 2010 und die Internationale Konferenz für Datenbanktheorie 2015. Auf dem ACM-Symposium 2011 für Prinzipien von Datenbanksystemen, der International Conference on Database Theory 2013 und dem ACM-Symposium 2014 über Prinzipien von Datenbanksystemen wurden 10-Jahres-Test-Time-Auszeichnungen für den Test-of-Time-Auszeichnungen mit 10-jährigen Time-Auszeichnungen gewonnen.

Arbeit

Fagins Theorem

Fagins Theorem, was er in seiner Doktorarbeit bewiesen hat, erklärt, dass existenziell existentiell Logik zweiter Ordnung fällt mit der Komplexitätsklasse zusammen Np in dem Sinne, dass ein Entscheidungsproblem in der existentiellen Logik zweiter Ordnung ausgedrückt werden kann, wenn es nur dann durch a gelöst werden kann Nichtdeterministische Turing-Maschine in Polynomzeit. Diese Arbeit half bei der Gründung des Bereichs von Finite -Modell -Theorie.[8][9]

Andere Beiträge

Ein weiteres Ergebnis, das er in seiner Doktorarbeit bewiesen hat, ist, dass Logik erster Ordnung ein Null-Ein-Gesetz hat, das besagt -Node -Strukturen, die S erfüllen, konvergiert, wenn n in unendlich ist und tatsächlich auf 0 oder 1 konvergiert.[10] Dieses Ergebnis wurde unabhängig von Glebskiĭ et al. Früher (1969) in Russland,[11] mit einem ganz anderen Beweis.

Er ist auch bekannt für seine Arbeit an höher Normale Formen in Datenbanktheorie, im Speziellen 4nf, 5nf und DK/NF.

Neben Fagins Theorem sind andere nach Fagin benannte Konzepte "Fagins Algorithmus" zur Score -Aggregation.[12] Das "Fagin-Invers" für den Datenaustausch,[13] und "Fagin -Spiele"[14] und "Ajtai Fagin Games"[15] Zum Nachweis der Unpressbarkeit führt zu einer Logik.

Veröffentlichungen

Fagin hat zahlreiche Artikel verfasst oder mitautorisiert.[16][17] und ein Buch:

  • Ronald Fagin, Joseph Y. Halpern, Yoram Moses und Moshe Y. Vardi. Argumentation über Wissen. Mit Press (1995). Taschenbuchausgabe (2003).

Artikel, eine Auswahl:

  • Ronald Fagin. "Verallgemeinerte Spektren erster Ordnung und polynomiale Zeit erkennbare Mengen". Komplexität der Berechnung, hrsg. R. Karp, Siam-Ams Proceedings, Vol. Vol. 7 (1974): 43-73.
  • Ronald Fagin, Jurg Nievergelt, Nicholas J. Pippenger und H. Raymond Strong. "Erweiterbares Hashing - eine schnelle Zugriffsmethode für dynamische Dateien." ACM -Transaktionen auf Datenbanksystemen (TODS) 4.3 (1979): 315–344.
  • Ronald Fagin, Amnon Lotem und Moni Naor. "Optimale Aggregationsalgorithmen für Middleware." Journal of Computer and System Sciences 66 (2003): 614–656. (Sonderausgabe für ausgewählte Arbeiten aus dem ACM -Symposium 2001 über Prinzipien von Datenbanksystemen).
  • Ronald Fagin, Phokion G. Kolaitis, Renee J Miller und Lucian Popa. "Datenaustausch: Semantik und Abfrage antworten", Theoretische Informatik 336 (2005): 89-124. (Sonderausgabe für ausgewählte Artikel aus der Internationalen Konferenz von 2003 zur Datenbanktheorie).

Verweise

  1. ^ Ronald Fagin, Joseph Y. Halpern, Yoram Moses und Moshe Y. Vardi, Begründung über Wissen, MIT Press, 1995. Taschenbuch Edition, 2003.
  2. ^ Ronald Fagin, Amnon Lotem und Moni Naor., "Optimale Aggregationsalgorithmen für Middleware". Journal of Computer and System Sciences 66 (2003): 614-656. Erweiterte Zusammenfassung erschien in Proc. 2001 ACM-Symposium über Prinzipien von Datenbanksystemen, S. 102-113.
  3. ^ IEEE Computer Society Namen 2011 Technische Gewinner
  4. ^ Der Edward J. McCluskey Technical Achievement Award
  5. ^ ACM Sigmod Edgar F. Codd Innovations Award
  6. ^ Ronald Fagin, Phokion Kolaitis, Renee J. Miller und Lucian Popa, „Datenaustausch: Semantik und Abfrage antworten“, Theoretische Informatik 336 (2005): 89-124. (Sonderausgabe für ausgewählte Artikel aus der Internationalen Konferenz von 2003 zur Datenbanktheorie).
  7. ^ Ronald Fagin, Phokion G. Kolaitis, Lucian Popa und Wang-Chiew Tan, "Komponieren von Schema-Zuordnungen: Abhängigkeiten zweiter Ordnung von der Rettung", ACM Trans. auf Datenbanksystemen 30, 4 (Dezember 2005), S. 994-1055. (Sonderausgabe für ausgewählte Arbeiten der ACM Sigmod/Pods -Konferenz von 2004).
  8. ^ Neil Immerman, Beschreibende Komplexität. Springer-Verlag, 1999.
  9. ^ Leonid Libkin, Elemente der endlichen Modelltheorie. Springer 2004. ISBN978-3-540-21202-7.
  10. ^ Ronald Fagin: "Wahrscheinlichkeiten für endliche Modelle". Journal of Symbolic Logic, 41 (1): 50-58, 1976
  11. ^ Y.v. Glebskiĭ, D.I. Kogan, M.I. Liogonkiĭ und V.A. Talanov: "Reichweite und Grad der Realisierbarkeit von Formeln im eingeschränkten Prädikat -Kalkül." Kibernetika, 2: 17-28, 1969
  12. ^ Ronald Fagin. "Kombinieren Sie Fuzzy -Informationen aus mehreren Systemen." Journal of Computer and System Sciences 58 (1999): 83-99. (Sonderausgabe für ausgewählte Arbeiten aus dem ACM -Symposium von 1996 über Prinzipien von Datenbanksystemen).
  13. ^ Ronald Fagin, "Inverting Schema Mappings". ACM trans. Auf Datenbanksystemen 32, 4, November 2007. (Sonderausgabe für ausgewählte Arbeiten aus dem ACM -Symposium 2006 über Prinzipien von Datenbanksystemen.)
  14. ^ Ronald Fagin, "Monadische verallgemeinerte Spektren". Zeitschr. f. Mathematik. Logik und Grundlagen d. Mathematik. 21, 1975, S. 89-96.
  15. ^ Miklos Ajtai und Ronald Fagin, "Die Erreichbarkeit ist für die gerichtete Richtlinie schwieriger als für ungerichtete endliche Graphen". Journal of Symbolic Logic 55, 1. März 1990, S. 113-150. Vorläufige Version erschien in Proc. 29. IEEE-Symposium für Fundamente der Informatik, 1988, S. 358-367.
  16. ^ Ronald Fagin: IBM Almaden Research Center Google Scholar -Profil
  17. ^ Ronald Fagin Die DBLP -Informatik -Bibliographie

Externe Links