Ronald Fagin

Last updated
Ronald Fagin
Ronald Fagin, IBM Researcher.jpg
Ronald Fagin
Born1945 (age 78–79)
Oklahoma City, OK, U.S.
Nationality American
Alma mater Dartmouth College,
University of California, Berkeley
Known for Fagin's theorem
Awards Gödel prize (2014),
W. Wallace McDowell Award (2012),
SIGMOD Edgar F. Codd Innovations Award (2004)
Scientific career
Fields Logic in Computer Science,
Database theory,
Finite model theory,
Rank and score aggregation,
Reasoning about knowledge
Institutions IBM Almaden Research Center
Doctoral advisor Robert Lawson Vaught

Ronald Fagin (born 1945) is an American mathematician and computer scientist, and IBM Fellow at the IBM Almaden Research Center. He is known for his work in database theory, finite model theory, and reasoning about knowledge. [1]

Contents

Biography

Ron Fagin was born and grew up in Oklahoma City, where he attended Northwest Classen High School. He was later elected to the Northwest Classen Hall of Fame. He completed his undergraduate degree at Dartmouth College. Fagin received his Ph.D. in Mathematics from the University of California, Berkeley in 1973, where he worked under the supervision of Robert Vaught.

He joined the IBM Research Division in 1973, spending two years at the Thomas J. Watson Research Center, and then transferred in 1975 to what is now the IBM Almaden Research Center in San Jose, California.

He has served as program committee chair for ACM Symposium on Principles of Database Systems 1984, Theoretical Aspects of Reasoning about Knowledge 1994, ACM Symposium on Theory of Computing 2005, and the International Conference on Database Theory 2009.

Fagin has received numerous professional awards for his work. He is a Member of the National Academy of Sciences, National Academy of Engineering, and American Academy of Arts and Sciences. He is an IBM Fellow, ACM Fellow, IEEE Fellow, Fellow of the American Association for the Advancement of Science, and Fellow of Asia-Pacific Artificial Intelligence Association. One of his papers [2] won the Gödel Prize. He received a Docteur Honoris Causa from the University of Paris, and a Laurea Honoris Causa from the University of Calabria in Italy. The IEEE granted him the IEEE W. Wallace McDowell Award and the IEEE Technical Achievement Award [3] (now known as the Edward J. McCluskey Technical Achievement Award [4] ); and the ACM granted him the ACM SIGMOD Edgar F. Codd Innovations Award The European Association for Theoretical Computer Science (in conjunction with the ACM Special Interest Group for Logic and Computation, the European Association for Computer Science Logic, and the Kurt Gödel Society) granted him and the co-authors of two of his papers, [5] [6] the Alonzo Church Award for Logic and Computation. IBM granted him eight IBM Outstanding Innovation Awards, two IBM supplemental Patent Issue Awards, given for key IBM patents, three IBM Outstanding Technical Achievement Awards, and two IBM Corporate Awards. He won Best Paper awards at the 1985 International Joint Conference on Artificial Intelligence, the 2001 ACM Symposium on Principles of Database Systems, the 2010 International Conference on Database Theory, and the 2015 International Conference on Database Theory. He won 10-year Test-of-Time Awards at the 2011 ACM Symposium on Principles of Database Systems, the 2013 International Conference on Database Theory, and the 2014 ACM Symposium on Principles of Database Systems.

Work

Fagin's theorem

Fagin's theorem, which he proved in his PhD thesis, states that existential second-order logic coincides with the complexity class NP in the sense that a decision problem can be expressed in existential second-order logic if and only if it can be solved by a non-deterministic Turing machine in polynomial time. This work helped found the area of finite model theory. [7] [8]

Other contributions

Another result that he proved in his PhD thesis is that first-order logic has a zero-one law, which says that if S is a first-order sentence with only relational symbols (no function or constant symbols), then the fraction of n-node structures that satisfy S converges as n goes to infinity, and in fact converges to 0 or 1. [9] This result was proved independently by Glebskiĭ and co-authors earlier (1969) in Russia, [10] with a very different proof.

He is also known for his work on higher normal forms in database theory, particularly 4NF, 5NF and DK/NF.

Besides Fagin's theorem, other concepts named after Fagin are "Fagin's algorithm" for score aggregation, [11] the "Fagin-inverse" for data exchange, [12] and "Fagin games" [13] and "Ajtai–Fagin games" [14] for proving inexpressibility results in logic.

Publications

Fagin has authored or co-authored numerous articles, [15] [16] and a book:

Articles, a selection:

Related Research Articles

The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membership group, reporting nearly 110,000 student and professional members as of 2022. Its headquarters are in New York City.

<span class="mw-page-title-main">Leslie Lamport</span> American computer scientist and mathematician

Leslie B. Lamport is an American computer scientist and mathematician. Lamport is best known for his seminal work in distributed systems, and as the initial developer of the document preparation system LaTeX and the author of its first manual.

<span class="mw-page-title-main">Charles Bachman</span> American computer scientist

Charles William Bachman III was an American computer scientist, who spent his entire career as an industrial researcher, developer, and manager rather than in academia. He was particularly known for his work in the early development of database management systems. His techniques of layered architecture include his namesake Bachman diagrams.

Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe.

<span class="mw-page-title-main">Paris Kanellakis</span> American computer scientist (1953–1995)

Paris Christos Kanellakis was a Greek American computer scientist.

Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithms for solving those problems. The theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP.

Brent Hailpern is a computer scientist retired from IBM Research. His research work focused on programming languages, software engineering, and concurrency.

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.

<span class="mw-page-title-main">Moshe Vardi</span> Israeli mathematicien and computer scientist

Moshe Ya'akov Vardi is an Israeli mathematician and computer scientist. He is the Karen Ostrum George Distinguished Service Professor in Computational Engineering at Rice University, United States. and a faculty advisor for the Ken Kennedy Institute. His interests focus on applications of logic to computer science, including database theory, finite model theory, knowledge of multi-agent systems, computer-aided verification and reasoning, and teaching logic across the curriculum. He is an expert in model checking, constraint satisfaction and database theory, common knowledge (logic), and theoretical computer science.

<span class="mw-page-title-main">Mihalis Yannakakis</span> Greek-American computer scientist

Mihalis Yannakakis is professor of computer science at Columbia University. He is noted for his work in computational complexity, databases, and other related fields. He won the Donald E. Knuth Prize in 2005.

<span class="mw-page-title-main">Georg Gottlob</span> Austrian computer scientist

Georg Gottlob FRS is an Austrian-Italian computer scientist who works in the areas of database theory, logic, and artificial intelligence and is Professor of Informatics at the University of Calabria. He was Professor at the University of Oxford.

Ashok K. Chandra was a computer scientist at Microsoft Research in Mountain View, California, United States, where he was a general manager at the Internet Services Research Center. Chandra received his PhD in Computer Science from Stanford University, an MS from University of California, Berkeley, and a BTech from IIT Kanpur. He was previously Director of Database and Distributed Systems at IBM Almaden Research Center.

In relational database theory, a tuple-generating dependency (TGD) is a certain kind of constraint on a relational database. It is a subclass of the class of embedded dependencies (EDs).

Leonid Libkin is a computer scientist who works in data management, in particular in database theory, and in logic in computer science.

ACM SIGLOG or SIGLOG is the Association for Computing Machinery Special Interest Group on Logic and Computation. It publishes a news magazine, and has the annual ACM-IEEE Symposium on Logic in Computer Science (LICS) as its flagship conference. In addition, it publishes an online newsletter, the SIGLOG Monthly Bulletin, and "maintains close ties" with the related academic journal ACM Transactions on Computational Logic.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

Phokion G. KolaitisACM is a computer scientist who is currently a Distinguished Research Professor at UC Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity.

<span class="mw-page-title-main">Nicola Leone</span> Italian computer scientist

Nicola Leone is an Italian computer scientist who works in the areas of artificial intelligence, knowledge representation and reasoning, and database theory. Leone is currently the rector of the University of Calabria and a professor of Computer Science. Previously, he was a professor of Database Systems at the TU Wien.

References

  1. ↑ Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi, Reasoning about Knowledge, MIT Press, 1995. Paperback edition, 2003.
  2. ↑ Ronald Fagin, Amnon Lotem, and Moni Naor., "Optimal aggregation algorithms for middleware". Journal of Computer and System Sciences 66 (2003): 614-656. Extended abstract appeared in Proc. 2001 ACM Symposium on Principles of Database Systems, pp. 102-113.
  3. ↑ IEEE Computer Society Names 2011 Technical Winners
  4. ↑ The Edward J. McCluskey Technical Achievement Award
  5. ↑ Ronald Fagin, Phokion Kolaitis, Renee J Miller, and Lucian Popa, “Data exchange: semantics and query answering”, Theoretical Computer Science 336 (2005): 89-124. (Special issue for selected papers from the 2003 International Conference on Database Theory).
  6. ↑ Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan, “Composing schema mappings: Second-order dependencies to the rescue”, ACM Trans. on Database Systems 30, 4 (Dec. 2005), pp. 994-1055. (Special issue for selected papers from the 2004 ACM SIGMOD/PODS Conference).
  7. ↑ Neil Immerman, Descriptive Complexity . Springer-Verlag, 1999.
  8. ↑ Leonid Libkin, Elements of Finite Model Theory. Springer 2004. ISBN   978-3-540-21202-7.
  9. ↑ Ronald Fagin: "Probabilities on Finite Models". Journal of Symbolic Logic, 41(1):50-58, 1976
  10. ↑ Glebskiĭ, Y. V.; Kogan, D. I.; Liogonkiĭ, M. I.; Talanov, V. A. (1969). "Range and degree of realizability of formulas in the restricted predicate calculus". Kibernetika. 5 (2): 17–28. doi:10.1007/bf01071084. S2CID   121409759.
  11. ↑ Ronald Fagin. "Combining fuzzy information from multiple systems." Journal of Computer and System Sciences 58 (1999): 83-99. (Special issue for selected papers from the 1996 ACM Symposium on Principles of Database Systems).
  12. ↑ Ronald Fagin, "Inverting schema mappings". ACM Trans. on Database Systems 32, 4, Nov. 2007. (Special issue for selected papers from the 2006 ACM Symposium on Principles of Database Systems.)
  13. ↑ Ronald Fagin, "Monadic generalized spectra". Zeitschr. f. math. Logik und Grundlagen d. Math. 21, 1975, pp. 89-96.
  14. ↑ Miklos Ajtai and Ronald Fagin, "Reachability is harder for directed than for undirected finite graphs". Journal of Symbolic Logic 55, 1, March 1990, pp. 113-150. Preliminary version appeared in Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 358-367.
  15. ↑ Ronald Fagin publications indexed by Google Scholar OOjs UI icon edit-ltr-progressive.svg
  16. ↑ Ronald Fagin at DBLP Bibliography Server OOjs UI icon edit-ltr-progressive.svg
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.