ロナルド・フェイギン

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
ロナルド・フェイギン
Ronald Fagin
Fagin.jpg
ロナルド・フェイギン
生誕 (1945-05-01) 1945年5月1日(71歳)
アメリカ合衆国の旗 アメリカ合衆国
オクラホマ州オクラホマシティ
居住 アメリカ合衆国の旗 アメリカ合衆国
カリフォルニア州ロサンゼルス
国籍 アメリカ合衆国の旗 アメリカ合衆国
研究分野 コンピュータ科学における論理学
データベース理論
有限モデル理論
ナレッジについての推論
研究機関 IBMアルマデン・リサーチ・センター英語版
出身校 ダートマス大学
カリフォルニア大学バークレー校
博士課程
指導教員
ロバート・ヴォート英語版
主な業績 フェイギンの定理英語版
主な受賞歴 ゲーデル賞(2014)
プロジェクト:人物伝

ロナルド・フェイギン: Ronald Fagin)は、IBMアルマデン・リサーチ・センター英語版の計算機科学基礎理論グループ統括責任者である。フェイギンは、データベース理論、有限モデル理論、知識推論についての先駆的な業績で知られている[1]。フェイギンはその業績により、多くの表彰を受けている。

略歴[編集]

若年期[編集]

フェイギンは1945年5月1日にアメリカ合衆国オクラホマ州オクラホマシティで生まれた。ダートマス大学で学士号を取得した後、ロバート・ヴォート英語版の指導を受け1973年にカリフォルニア大学バークレー校で博士号を取得した。1973年にIBM研究部門に入り、トーマス・J・ワトソン研究所で2年過ごした後、1975年にカリフォルニア州サンノゼにあるIBMアルマデン・リサーチ・センター英語版へ異動した。

業績[編集]

フェイギンが博士論文で証明したフェイギンの定理英語版は、非決定性チューリングマシンによって多項式時間で解くことができる場合に限り決定問題は存在論的二階述語論理で表現することができるという意味において、存在論的二階述語論理は複雑性クラスNPと一致すると述べたものである。この証明は有限モデル理論の分野に大きな影響を与えた[2]。フェイギンによる証明で他に有名なものとしては、一階述語論理における0-1法則の存在と、この法則を用いたデータベースクエリ言語の表現不可能性の証明がある[3]。これはロシアにおいてわずかに早くグレプスキーらによって証明された[4]。 フェイギンはまたデータベース理論における正規形、特に第4正規形の研究で知られている。

フェイギンは、データベースシステムの原理に関するACMシンポジウム(1984年)[5]、知識推論の理論的側面についての国際会議(1994年)[6]、計算理論に関するACMシンポジウム(2005年)[7]、データベース理論に関する国際会議(2009年)[8]でプログラム委員長を務めている。

受賞歴・フェロー等[編集]

関連項目[編集]

脚注[編集]

  1. ^ Reasoning about Knowledge. Co-authors J.Y. Halpern, Y. Moses and M.Y. Vardi. Published by MIT Press, 1995. Paperback edition, 2003.
  2. ^ Neil Immerman, Descriptive Complexity. Springer-Verlag, 1999
  3. ^ Ronald Fagin: Probabilities on Finite Models. Journal of Symbolic Logic, 41(1):50-58, 1976
  4. ^ 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
  5. ^ ACM Symposium on Principles of Database Systems 1984
  6. ^ Theoretical Aspects of Reasoning about Knowledge 1994
  7. ^ Symposium on Theory of Computing 2005
  8. ^ International Conference on Database Theory 2009

外部リンク[編集]