Revision by History

Journal of Artificial Intelligence Research

This article proposes a solution to the problem of obtaining plausibility information, which is necessary to perform belief revision: given a sequence of revisions, together with their results, derive a possible initial order that has generated them; this is different from the usual assumption of starting from an all-equal initial order and modifying it by a sequence of revisions. Four semantics for iterated revision are considered: natural, restrained, lexicographic and reinforcement. For each, a necessary and sufficient condition to the existence of an order generating a given history of revisions and results is proved. Complexity is proved coNP complete in all cases but one (reinforcement revision with unbounded sequence length).

 @article{libe-15,
 title = {Revision by History},
 year = {2015},
 author = {Paolo Liberatore},
 journal = {Journal of Artificial Intelligence Research},
 pages = {287-329},
 volume = {52},
 }