On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals
Summary: Classifies complexity of deciding whether q follows from T ◦ p for many propositional revision/update operators (Cross-Product, WIDTIO, Dalal, Forbus, Borgida, Winslett, Satoh, Weber), in general and for Horn T or |p|-bounded cases. Assesses adherence to Minimality of Change and pinpoints exact complexity thresholds and tractable fragments. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Thomas Eiter
- 2. Georg Gottlob
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,102 | On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases | 2003 | PODS | 0.00014049364 |
| 5,767 | Data Exchange beyond Complete Data | 2011 | PODS | 5.3334039e-05 |
| 12,795 | The Size of a Revised Knowledge Base | 1995 | PODS | 4.1945683e-05 |
| 12,830 | Object Migration | 1994 | PODS | 4.1945683e-05 |
| 12,849 | Cumulative Updates | 1994 | VLDB | 4.1945683e-05 |
| 12,855 | On the Semantics of Theory Change: Arbitration between Old and New Information | 1993 | PODS | 4.1945683e-05 |
| 12,888 | Knowledgebase Transformations | 1992 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 556 | On the Semantics of Updates in Databases | 1983 | PODS | 0.00020249905 |
| 4,255 | Hypothetical Datalog: Negation and Linear Recursion | 1989 | PODS | 6.3212356e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,601 | Conjunctive Queries on Probabilistic Graphs: Combined Complexity | 2017 | PODS | 4.698961e-05 |
| 7,739 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 4.663547e-05 |
| 14,168 | The Complexity of Reusing and Modifying Rulebases | 1992 | PODS | - |
| 2,243 | The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints | 2015 | PODS | 9.2166927e-05 |
| 7,598 | Polynomial-time program transformations in deductive databases | 1990 | PODS | 4.7004867e-05 |
| 12,954 | A Framework for Comparison of Update Semantics (Extended Abstract) | 1988 | PODS | 4.1945683e-05 |
| 12,888 | Knowledgebase Transformations | 1992 | PODS | 4.1945683e-05 |
| 13,755 | Knowledge compilation = Query rewriting + View synthesis | 2002 | PODS | - |
| 6,522 | Complexity Aspects of Various Semantics for Disjunctive Databases | 1993 | PODS | 5.0287573e-05 |
| 12,795 | The Size of a Revised Knowledge Base | 1995 | PODS | 4.1945683e-05 |