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)

Paper ID: h406a8ca3ffcea12a
Venue: PODS
Year: 1992
Pagerank: 8.3008262e-05
Overall Rank: 2,557 | 82.81%
DOI: 10.1145/137097.137886

Incoming Non-self Citations Over Time

Authors

1. Thomas Eiter (Vienna University of Technology)
2. Georg Gottlob (Vienna University of Technology)

BibTeX Citation

@inproceedings{eiter_pods92,
        address = {New York, NY, USA},
        series = {{PODS} '92},
        title = {{On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals}},
        url = {https://dl.acm.org/doi/10.1145/137097.137886},
        doi = {10.1145/137097.137886},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Eiter, Thomas and Gottlob, Georg},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013204612
4,532	Data Exchange beyond Complete Data	2011	PODS	6.5583849e-05
13,279	The Size of a Revised Knowledge Base	1995	PODS	4.9793485e-05
13,314	Object Migration	1994	PODS	4.9793485e-05
13,332	Cumulative Updates	1994	VLDB	4.9793485e-05
13,338	On the Semantics of Theory Change: Arbitration between Old and New Information	1993	PODS	4.9793485e-05
13,372	Knowledgebase Transformations	1992	PODS	4.9793485e-05

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
619	On the Semantics of Updates in Databases	1983	PODS	0.00015518944
5,725	Hypothetical Datalog: Negation and Linear Recursion	1989	PODS	6.0169517e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,858	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
2	8,254	Symmetric Weighted First-Order Model Counting	2015	PODS
3	14,679	The Complexity of Reusing and Modifying Rulebases	1992	PODS
4	1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
5	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
6	13,439	A Framework for Comparison of Update Semantics (Extended Abstract)	1988	PODS
7	13,372	Knowledgebase Transformations	1992	PODS
8	14,267	Knowledge compilation = Query rewriting + View synthesis	2002	PODS
9	7,712	Complexity Aspects of Various Semantics for Disjunctive Databases	1993	PODS
10	13,279	The Size of a Revised Knowledge Base	1995	PODS