Let K be a knowledge base (KB) and let φ be new information, both propositional formulas expressed in conjunctive form (CF). We propose a deterministic and correct algorithm for performing the belief revision of φ in K, denoted as: K ∘ φ. Our proposal satisfies subsets of AGM and KM postulates. We also present the soundness proof of our belief revision method, and the analysis of its time complexity.
AlchourronC., GardenfordsP. and MakinsonD., On the logic of theory change: Partial meet contraction and revision functions, Journal of Symbolic Logic50 (1985), 510–530.
2.
BaralC. and ZhangY., Knowledge updates: Semantics and complexity issues, Artificial Intelligence164 (2005), 209–243.
3.
BoellaG., PigozziG. and TorreL.V., AGM contraction and revision of rules, J Log Lang Inf25 (2016), 273–297.
4.
DalalM., Investigations into theory of knowledge base revision, Proc The Seventh National Conference on Artificial Intelligence (1988), 475–479.
5.
DarwicheA. and PearlJ., On the logic of iterated belief revision, Artificial Intelligence89 (1997), 1–29.
6.
DarwicheA., On tractable counting of theory models and its application to truth maintenance and belief revision, Applied Non- Classical Logics11 (2001), 11–34.
7.
De ItaG., Marcial-RomeroR., HernándezJ. and Pozos-ParraP., Using binary patterns for counting falsifying assignments of conjunctive forms, Elect Notes in Theoretical Computer Science315 (2015), 17–30.
8.
JiangD., LiW., LuoJ., LouY. and LiaoZ., A representative model based algorithm for maximal contractions, Science China Information Sciences56 (2013), 1–13.
9.
EllisD., Irredundant families of subcubes, Mathematical Proceedings of the Cambridge Philosophical Society150 (2011), 257–272.
10.
FalappaM.A., GarciaA.J., IbsernerG.K. and SimariG.R., Stratified belief bases revision with argumentative inference, J Philos Logic42 (2011), 161–193.
11.
FermeE. and HanssonS.O., AGM25 years twenty-five years of research in belief change, J Philos Logic40 (2011), 295–331.
12.
EiterT. and GottlobG., On the complexity of propositional knowledge base revision, updates and counterfactuals, Artificial Intelligence57 (1992), 227–270.
13.
HerzigA.Handbook of Defeasible Reasoning and Uncertainty Management (1998)189–231Logics for belief base updating, D. Dubois, D. Gabbay, H.rade, P. Smets (Eds.),, pp.
14.
KatsunoH. and MendelzonA.O., Propositional knowledge base revision and minimal change, Journal of Artificial Intelligence52 (1991), 387–394.
15.
KhardonR. and RothD., On the difference between updating a knowledge base and revising it, KR91 (1991), 387–394.
16.
KhardonR. and RothD., Reasoning with models, Artificial Intelligence87 (1996), 187–213.
17.
LiberatoreP., The complexity of belief update, Artificial Intelligence119 (2000), 141–190.
18.
LiberatoreP. and SchaerfM., The complexity of model checking for belief revision and update, Journal of Computer and Systems Sciences61 (2001), 43–72.
19.
NebelB., How hard is it to revise a belief base?Handbook of Defeasible Reasoning and Uncertainty Management Systems3 (1998), 77–145.
20.
HanssonS.O., A monoselective presentation of AGM revision, Studia Logica103 (2014), 1019–1033.
21.
LiuW., PozosP. and PerrusselL., Dalal’s revision without hamming distance, 12th Mexican International Conference on Artificial Intelligence (2013), 41–53.
22.
PeppasaP., WilliansM.A., ChopracS. and FooN., Relevance in belief revision, Artificial Intelligence229 (2015), 126–138.
23.
SatohK., Nonmonotonic reasoning by minimal belief revision, Institute for New Generation Computer Technology358 (1988), 157–170.
24.
SelmanB., Tractable Default Reasoning, Phd. Dissertation, Department of Computer Science University of Toronto; 1990.
25.
ZhuangZ., PagnuccoM. and ZhangY., Inter-definability of horn contraction and horn revision, J Philos Logic46 (2016), 299–332.
