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,101 | On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases | 2003 | PODS | 0.00014037952 |
| 5,775 | Data Exchange beyond Complete Data | 2011 | PODS | 5.3282847e-05 |
| 12,804 | The Size of a Revised Knowledge Base | 1995 | PODS | 4.1905499e-05 |
| 12,839 | Object Migration | 1994 | PODS | 4.1905499e-05 |
| 12,858 | Cumulative Updates | 1994 | VLDB | 4.1905499e-05 |
| 12,864 | On the Semantics of Theory Change: Arbitration between Old and New Information | 1993 | PODS | 4.1905499e-05 |
| 12,898 | Knowledgebase Transformations | 1992 | PODS | 4.1905499e-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 |
|---|---|---|---|---|
| 555 | On the Semantics of Updates in Databases | 1983 | PODS | 0.00020229919 |
| 4,251 | Hypothetical Datalog: Negation and Linear Recursion | 1989 | PODS | 6.3149914e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,604 | Conjunctive Queries on Probabilistic Graphs: Combined Complexity | 2017 | PODS | 4.6944524e-05 |
| 7,738 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 4.6590737e-05 |
| 14,182 | The Complexity of Reusing and Modifying Rulebases | 1992 | PODS | - |
| 2,246 | The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints | 2015 | PODS | 9.2039096e-05 |
| 7,603 | Polynomial-time program transformations in deductive databases | 1990 | PODS | 4.6959912e-05 |
| 12,964 | A Framework for Comparison of Update Semantics (Extended Abstract) | 1988 | PODS | 4.1905499e-05 |
| 12,898 | Knowledgebase Transformations | 1992 | PODS | 4.1905499e-05 |
| 13,769 | Knowledge compilation = Query rewriting + View synthesis | 2002 | PODS | - |
| 6,519 | Complexity Aspects of Various Semantics for Disjunctive Databases | 1993 | PODS | 5.0239231e-05 |
| 12,804 | The Size of a Revised Knowledge Base | 1995 | PODS | 4.1905499e-05 |