Ronald Fagin

Orcid: 0000-0002-7374-0347

Affiliations:
  • IBM Almaden Research Center, San Jose, USA


According to our database1, Ronald Fagin authored at least 162 papers between 1975 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2000, "For creating the field of finite model theory, and for fundamental research in relational database theory and in reasoning about knowledge.".

IEEE Fellow

IEEE Fellow 1997, "For contributions to finite-model theory, and to relational database theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Parallel Play Saves Quantifiers.
CoRR, 2024

Combining Entity Resolution and Query Answering in Ontologies: A Formal Conceptual Framework.
Proceedings of the 32nd Symposium of Advanced Database Systems, 2024

On the Number of Quantifiers Needed to Define Boolean Functions.
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023
A Finer Analysis of Multi-Structural Games and Beyond.
CoRR, 2023

A Framework for Combining Entity Resolution and Query Answering in Knowledge Bases.
Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, 2023

2022
On the Number of Quantifiers as a Complexity Measure.
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

2021
Panel on "Past and Future of Computer Science Theory" (Discussion Paper).
Proceedings of the 29th Italian Symposium on Advanced Database Systems, 2021

Multi-Structural Games and Number of Quantifiers.
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Ontology-Enriched Query Answering on Relational Databases.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
Foundations of Reasoning with Uncertainty via Real-valued Logics.
CoRR, 2020

Logical Neural Networks.
CoRR, 2020

2019
Expressive power of entity-linking frameworks.
J. Comput. Syst. Sci., 2019

Recursive Programs for Document Spanners.
Proceedings of the 22nd International Conference on Database Theory, 2019

2018
Tuple-Generating Dependencies.
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

Score Aggregation.
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

Equality-Generating Dependencies.
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

2016
Declarative Cleaning of Inconsistencies in Information Extraction.
ACM Trans. Database Syst., 2016

A Declarative Framework for Linking Entities.
ACM Trans. Database Syst., 2016

An Algorithmic View of Voting.
SIAM J. Discret. Math., 2016

Optimal Score Aggregation Algorithms.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

2015
A Relational Framework for Information Extraction.
SIGMOD Rec., 2015

Document Spanners: A Formal Approach to Information Extraction.
J. ACM, 2015

Dichotomies in the Complexity of Preferred Repairs.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

2014
Cleaning inconsistencies in information extraction via prioritized repairs.
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

The ICDT 2014 Test of Time Award.
Proceedings of the Proc. 17th International Conference on Database Theory (ICDT), 2014

2013
Solutions and query rewriting in data exchange.
Inf. Comput., 2013

Spanners: a formal framework for information extraction.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Applying theory to practice.
Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, 2013

2012
Local transformations and conjunctive-query equivalence.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

A normal form for preventing redundant tuples in relational databases.
Proceedings of the 15th International Conference on Database Theory, 2012

2011
Reverse data exchange: Coping with nulls.
ACM Trans. Database Syst., 2011

Foreword.
Theory Comput. Syst., 2011

Probabilistic data exchange.
J. ACM, 2011

Composition with Target Constraints
Log. Methods Comput. Sci., 2011

Rewrite rules for search database systems.
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Schema Mapping Evolution Through Composition and Inversion.
Proceedings of the Schema Matching and Mapping, 2011

2010
The structure of inverses in schema mappings.
J. ACM, 2010

Epistemic privacy.
J. ACM, 2010

Understanding queries in a search database system.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

2009
Tuple-Generating Dependencies.
Proceedings of the Encyclopedia of Database Systems, 2009

Equality-Generating Dependencies.
Proceedings of the Encyclopedia of Database Systems, 2009

Clio: Schema Mapping Creation and Data Exchange.
Proceedings of the Conceptual Modeling: Foundations and Applications, 2009

Finite Model Theory and its Origins.
Proceedings of the Conceptual Modelling 2009, 2009

2008
Quasi-inverses of schema mappings.
ACM Trans. Database Syst., 2008

Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03).
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2008

Towards a theory of schema-mapping optimization.
Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

2007
Inverting schema mappings.
ACM Trans. Database Syst., 2007

2006
Comparing Partial Rankings.
SIAM J. Discret. Math., 2006

2005
Composing schema mappings: Second-order dependencies to the rescue.
ACM Trans. Database Syst., 2005

Data exchange: getting to the core.
ACM Trans. Database Syst., 2005

Data exchange: semantics and query answering.
Theor. Comput. Sci., 2005

Efficient Implementation of Large-Scale Multi-Structural Databases.
Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30, 2005

Multi-structural databases.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

2004
Comparing and Aggregating Rankings with Ties.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Locally Consistent Transformations and Query Answering in Data Exchange.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

2003
Comparing Top k Lists.
SIAM J. Discret. Math., 2003

Optimal aggregation algorithms for middleware.
J. Comput. Syst. Sci., 2003

Searching the workplace web.
Proceedings of the Twelfth International World Wide Web Conference, 2003

Efficient similarity search and classification via rank aggregation.
Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003

2002
Combining Fuzzy Information: an Overview.
SIGMOD Rec., 2002

Guest Editor's Foreword.
J. Comput. Syst. Sci., 2002

Query Strategies for Priced Information.
J. Comput. Syst. Sci., 2002

Compactly encoding unstructured inputs with differential compression.
J. ACM, 2002

Schema Management.
IEEE Data Eng. Bull., 2002

Translating Web Data.
Proceedings of 28th International Conference on Very Large Data Bases, 2002

2001
The Clio Project: Managing Heterogeneity.
SIGMOD Rec., 2001

Data-Driven Understanding and Refinement of Schema Mappings.
Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 2001

Static Index Pruning for Information Retrieval Systems.
Proceedings of the SIGIR 2001: Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2001

2000
A formula for incorporating weights into scoring rules.
Theor. Comput. Sci., 2000

The Closure of Monadic NP.
J. Comput. Syst. Sci., 2000

Random walks with "back buttons" (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Query strategies for priced information (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Allowing users to weight search terms.
Proceedings of the Computer-Assisted Information Retrieval (Recherche d'Information et ses Applications), 2000

Logic, Complexity, and Games.
Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000

1999
Combining Fuzzy Information from Multiple Systems.
J. Comput. Syst. Sci., 1999

The hierarchical approach to modeling knowledge and common knowledge.
Int. J. Game Theory, 1999

Common Knowledge Revisited.
Ann. Pure Appl. Log., 1999

1998
Relaxing the Triangle Inequality in Pattern Matching.
Int. J. Comput. Vis., 1998

The Closure of Monadic NP (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Fuzzy Queries in Multimedia Database Systems.
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

1997
On Winning Strategies in Ehrenfeucht-Fraïssé Games.
Theor. Comput. Sci., 1997

Comparing the Power of Games on Graphs.
Math. Log. Q., 1997

Reasoning about Knowledge: A Response by the Authors.
Minds Mach., 1997

Knowledge-Based Programs.
Distributed Comput., 1997

Incorporating User Preferences in Multimedia Queries.
Proceedings of the Database Theory, 1997

Spectra with Only Unary Function Symbols.
Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996
Comparing Information Without Leaking It.
Commun. ACM, 1996

Efficiently Extendible Mappings for Balanced Data Distribution.
Algorithmica, 1996

The Garlic Project.
Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 1996

Easier Ways to Win Logical Games.
Proceedings of the Descriptive Complexity and Finite Models, 1996

1995
On Monadic NP vs. Monadic co-NP
Inf. Comput., July, 1995

A Nonstandard Approach to the Logical Omniscience Problem.
Artif. Intell., 1995

Querying Multimedia Data from Multiple Repositories by Content: the Garlic Project.
Proceedings of the Visual Database Systems 3, 1995

Towards Heterogeneous Multimedia Information Systems: The Garlic Approach.
Proceedings of the Proceedings RIDE-DOM '95, Fifth International Workshop on Research Issues in Data Engineering, 1995

Reasoning About Knowledge.
MIT Press, ISBN: 9780262562003, 1995

Reasoning about knowledge.
MIT Press, ISBN: 0262061627, 1995

1994
A Quantitative Analysis of Modal Logic.
J. Symb. Log., 1994

Reasoning About Knowledge and Probability.
J. ACM, 1994

Comparing the Power of Monadic NP Games.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

An Operational Semantics for Knowledge Bases.
Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31, 1994

1993
Finite-Model Theory - A Personal Perspective.
Theor. Comput. Sci., 1993

Response to "Remarks on Two New Theorems of Date and Fagin".
SIGMOD Rec., 1993

On Monadic NP vs. Monadic co-NP (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
Simple Conditions for Guaranteeing Higher Normal Forms in Relational Databases.
ACM Trans. Database Syst., 1992

What Is an Inference Rule?
J. Symb. Log., 1992

What Can Machines Know? On the Properties of Knowledge in Distributed Systems.
J. ACM, 1992

Two Views of Belief: Belief as Generalized Probability and Belief as Evidence.
Artif. Intell., 1992

The Expressive Power of the Kierarchical Approach to Modeling Knowledge and Common Knowledge.
Proceedings of the 4th Conference on Theoretical Aspects of Reasoning about Knowledge, 1992

1991
A Model-Theoretic Analysis of Knowledge.
J. ACM, 1991

Uncertainty, belief, and probability.
Comput. Intell., 1991

1990
Reachability Is Harder for Directed than for Undirected Finite Graphs.
J. Symb. Log., 1990

A Logic for Reasoning about Probabilities
Inf. Comput., 1990

A new approach to updating beliefs.
Proceedings of the UAI '90: Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, 1990

1989
Modelling Knowledge and Action in Distributed Systems.
Distributed Comput., 1989

1988
I'm OK if you're OK: On the notion of trusting communication.
J. Philos. Log., 1988

Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Correction to "An equivalence between relational database dependencies and a fragment of propositional logic".
J. ACM, 1987

Belief, Awareness, and Limited Reasoning. .
Artif. Intell., 1987

1986
A Simple Characterization of Database Dependency Implication.
Inf. Process. Lett., 1986

Updating Logical Databases.
Adv. Comput. Res., 1986

Knowledge and Implicit Knowledge in a Distributed Environment: Preliminary Report.
Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

What Can Machines Know? On the Epistemic Properties of Machines.
Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, 1986

1985
Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions.
Theor. Comput. Sci., 1985

Decreasing the Nesting Depth of Expressions Involving Square Roots.
J. Symb. Comput., 1985

An Internal Semantics for Modal Logic: Preliminary Report
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

A Formal Model of Knowledge, Action, and Communication in Distributed Systems: Preliminary Report.
Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

Belief, Awareness, and Limited Reasoning: Preliminary Report.
Proceedings of the 9th International Joint Conference on Artificial Intelligence. Los Angeles, 1985

1984
Inclusion Dependencies and Their Interaction with Functional Dependencies.
J. Comput. Syst. Sci., 1984

On the Structure of Armstrong Relations for Functional Dependencies.
J. ACM, 1984

The Theory of Data Dependencies - An Overview.
Proceedings of the Automata, 1984

A Model-Theoretic Analysis of Knowledge: Preliminary Report
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Degrees of Acyclicity for Hypergraphs and Relational Database Schemes
J. ACM, July, 1983

On the Desirability of Acyclic Database Schemes
J. ACM, July, 1983

Tools for Template Dependencies.
SIAM J. Comput., 1983

Armstrong Databases for Functional and Inclusion Dependencies.
Inf. Process. Lett., 1983

A Fair Carpool Scheduling Algorithm.
IBM J. Res. Dev., 1983

On the Semantics of Updates in Databases.
Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1983

Acyclic Database Schemes (of Various Degrees): A Painless Introduction.
Proceedings of the CAAP'83, 1983

1982
A Simplified Universal Relation Assumption and Its Properties.
ACM Trans. Database Syst., 1982

Horn clauses and database dependencies.
J. ACM, 1982

1981
A Normal Form for Relational Databases That Is Based on Domians and Keys.
ACM Trans. Database Syst., 1981

A Note on the Existence of Continuous Functionals.
Theor. Comput. Sci., 1981

An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic.
J. ACM, 1981

Properties of Acyclic Database Schemes
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980
Horn Clauses and Database Dependencies (Extended Abstract)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
Extendible Hashing - A Fast Access Method for Dynamic Files.
ACM Trans. Database Syst., 1979

Normal Forms and Relational Database Operators.
Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, USA, May 30, 1979

1978
On an Authorization Mechanism.
ACM Trans. Database Syst., 1978

Efficient Calculation of Expected Miss Ratios in the Independent Reference Model.
SIAM J. Comput., 1978

Cold-Start vs. Warm-Start Miss Ratios.
Commun. ACM, 1978

1977
Multivalued Dependencies and a New Normal Form for Relational Databases.
ACM Trans. Database Syst., 1977

Asymptotic Miss Ratios over Independent References.
J. Comput. Syst. Sci., 1977

Functional Dependencies in a Relational Data Base and Propositional Logic.
IBM J. Res. Dev., 1977

The number of finite relational structures.
Discret. Math., 1977

The Decomposition Versus Synthetic Approach to Relational Database Design.
Proceedings of the Third International Conference on Very Large Data Bases, 1977

A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations.
Proceedings of the 1977 ACM SIGMOD International Conference on Management of Data, 1977

1976
Probabilities on Finite Models.
J. Symb. Log., 1976

The independence of miss ratio on page size.
J. ACM, 1976

A Counterintuitive Example of Computer Paging.
Commun. ACM, 1976

1975
A spectrum hierarchy.
Math. Log. Q., 1975

A two-cardinal characterization of double spectra.
Math. Log. Q., 1975

Monadic generalized spectra.
Math. Log. Q., 1975


  Loading...