ロナルド・フェイギン（英: 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]でプログラム委員長を務めている。
受賞歴・フェロー等
- (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アルマデン・リサーチ・センター)
脚注
- ^ Reasoning about Knowledge. Co-authors J.Y. Halpern, Y. Moses and M.Y. Vardi. Published by MIT Press, 1995. Paperback edition, 2003.
- ^ Neil Immerman, Descriptive Complexity. Springer-Verlag, 1999
- ^ Ronald Fagin: Probabilities on Finite Models. Journal of Symbolic Logic, 41(1):50-58, 1976
- ^ 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
- ^ ACM Symposium on Principles of Database Systems 1984
- ^ Theoretical Aspects of Reasoning about Knowledge 1994
- ^ Symposium on Theory of Computing 2005
- ^ International Conference on Database Theory 2009
外部リンク
- Ronald Fagin's Website at IBM