ロナルド・フェイギン

フェイギンは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]でプログラム委員長を務めている。