ロナルド・フェイギン

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

ロナルド・フェイギン（英: Ronald Fagin、1945年5月1日 - ）は、アメリカ合衆国の計算機科学者、データベース研究者。IBMアルマデン・リサーチ・センター（英語版）の計算機科学基礎理論グループ統括責任者である。フェイギンは、データベース理論、有限モデル理論、知識推論についての先駆的な業績で知られている[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]でプログラム委員長を務めている。

受賞歴・フェロー等

• IBMアカデミー（英語版）選考員
• ACM SIGMOD エドガー・F・コッド 革新賞
• ACMフェロー
• IEEEフェロー
• AAASフェロー
• パリ大学名誉博士号
• 情報科学研究所のISI最多被引用著者（英語版）[1]
• IBM最優秀技術革新賞を8回
• IBM最優秀技術功績賞
• IBM supplemental Patent Issue Awards（重要なIBM特許に与えられる賞）を2回
• IBM会社賞
• ベストペーパー賞 - 人工知能に関する国際共同会議（1985年）
• ベストペーパー賞 - データベースシステムの原理に関するACMシンポジウム（2001年）
• ベストペーパー賞 - データベース理論に関する国際会議（2010年）
• テスト・オブ・タイム賞 - データベースシステムの原理に関するACMシンポジウムの論文
• IEEE技術功績賞
• ゲーデル賞（2014年）

関連項目

• フェイギンの定理（英語版）
• IBMアルマデン・リサーチ・センター（英語版）

脚注

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

外部リンク

• Ronald Fagin's Website at IBM