## Revision by History

**Paolo Liberatore**
*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},
}

doi: 10.1613/jair.4608