ロナルド・フェイギン
フェイギンが博士論文で証明したフェイギンの定理(英語版)は、非決定性チューリングマシンによって多項式時間で解くことができる場合に限り決定問題は存在論的二階述語論理で表現することができるという意味において、存在論的二階述語論理は複雑性クラスNPと一致すると述べたものである。この証明は有限モデル理論の分野に大きな影響を与えた。フェイギンによる証明で他に有名なものとしては、一階述語論理における0-1法則の存在と、この法則を用いたデータベースクエリ言語の表現不可能性の証明がある。これはロシアにおいてわずかに早くグレプスキーらによって証明された。 フェイギンはまたデータベース理論における正規形、特に第4正規形の研究で知られている。
フェイギンは、データベースシステムの原理に関するACMシンポジウム(1984年)、知識推論の理論的側面についての国際会議(1994年)、計算理論に関するACMシンポジウム(2005年)、データベース理論に関する国際会議(2009年)でプログラム委員長を務めている。