The Size of a Revised Knowledge Base
Summary: Studies, for propositional belief revision, the minimal-size formula equivalent to the revised KB and defines “compactability” (existence of polynomial-space representations). Shows some revision formalisms are compactable while others are provably non-compactable unless the polynomial hierarchy collapses, and links compactability to query-answering complexity beyond mere worst‑case class. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Marco Cadoli
- 2. Francesco M. Donini
- 3. Paolo Liberatore
- 4. Marco Schaerf
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
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 |
| 2,578 | On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals | 1992 | PODS | 8.5091045e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,826 | Bounded Query Rewriting Using Views | 2016 | PODS | 4.1945683e-05 |
| 5,638 | Circuit Treewidth, Sentential Decision, and Query Compilation | 2017 | PODS | 5.3965476e-05 |
| 7,739 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 4.663547e-05 |
| 6,365 | On the Expected Size of Recursive Datalog Queries | 1991 | PODS | 5.0945408e-05 |
| 827 | On the Representation and Querying of Sets of Possible Worlds | 1987 | SIGMOD | 0.00016220185 |
| 6,522 | Complexity Aspects of Various Semantics for Disjunctive Databases | 1993 | PODS | 5.0287573e-05 |
| 12,888 | Knowledgebase Transformations | 1992 | PODS | 4.1945683e-05 |
| 11,644 | Compiling Existential-Positive Queries to Bounded-Variable Fragments | 2019 | PODS | 4.1945683e-05 |
| 13,755 | Knowledge compilation = Query rewriting + View synthesis | 2002 | PODS | - |
| 2,578 | On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals | 1992 | PODS | 8.5091045e-05 |