Fagin
contemporaryMathematical Logic, Epistemic Logic, Theoretical Computer Scienceb. 1945
Ronald Fagin is an American logician and computer scientist at IBM Research known for foundational contributions to finite model theory, database theory, and epistemic logic. His work bridges mathematical logic and computation, most notably through the co-authorship of 'Reasoning About Knowledge,' which established formal frameworks for analyzing knowledge, belief, and plausibility in multi-agent systems. His results connecting descriptive complexity to computational complexity classes remain central to theoretical computer science.
Notable Achievements
1
Co-authored 'Reasoning About Knowledge' (1995), a foundational text in epistemic and doxastic logic
2
Proved Fagin's theorem: NP equals the class of problems expressible in existential second-order logic
3
Developed Fourth Normal Form (4NF) for relational database design
4
Contributed to the formal study of plausibility and belief revision in game-theoretic settings
5
Pioneered descriptive complexity theory linking logical expressibility to computational complexity