ロナルド・フェイギン

ロナルド・フェイギン（、1945年5月1日 - ）は、アメリカ合衆国の計算機科学者、データベース研究者。の計算機科学基礎理論グループ統括責任者である。フェイギンは、データベース理論、有限モデル理論、知識推論についての先駆的な業績で知られているReasoning about Knowledge. Co-authors J.Y. Halpern, Y. Moses and M.Y. Vardi. Published by MIT Press, 1995. Paperback edition, 2003.。フェイギンはその業績により、多くの表彰を受けている。

略歴若年期フェイギンはオクラホマ州オクラホマシティで生まれた。ダートマス大学で学士号を取得した後、の指導を受け1973年にカリフォルニア大学バークレー校で博士号を取得した。1973年にIBM研究部門に入り、トーマス・J・ワトソン研究所で2年過ごした後、1975年にカリフォルニア州サンノゼにあるへ異動した。

業績フェイギンが博士論文で証明したは、非決定性チューリングマシンによって多項式時間で解くことができる場合に限り決定問題は存在論的二階述語論理で表現することができるという意味において、存在論的二階述語論理は複雑性クラスNPと一致すると述べたものである。この証明は有限モデル理論の分野に大きな影響を与えたNeil Immerman, Descriptive Complexity. Springer-Verlag, 1999。フェイギンによる証明で他に有名なものとしては、一階述語論理における0-1法則の存在と、この法則を用いたデータベースクエリ言語の表現不可能性の証明がある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。フェイギンはまたデータベース理論における正規形、特に第4正規形の研究で知られている。

フェイギンは、データベースシステムの原理に関するACMシンポジウム（1984年）ACM Symposium on Principles of Database Systems 1984、知識推論の理論的側面についての国際会議（1994年）Theoretical Aspects of Reasoning about Knowledge 1994、計算理論に関するACMシンポジウム（2005年）Symposium on Theory of Computing 2005、データベース理論に関する国際会議（2009年）International Conference on Database Theory 2009でプログラム委員長を務めている。

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

ロナルド・フェイギン

Źródło i licencja