Can we forget how we learned? Doxastic redundancy in iterated belief revision
This addresses a theoretical issue in belief revision for AI and logic, but it is incremental as it builds on existing operators and complexity results.
The paper tackles the problem of determining whether forgetting a belief acquisition episode leads to information loss in iterated belief revision, and provides an algorithm for checking this for various revision operators, which may take exponential time in the worst case as the problem is coNP-hard.
Forgetting a belief acquisition episode may not cause information loss because of the others. Checking whether it does is not obvious, as the contribution of each belief revision is not isolated from the others, and the same information may be given not directly but by deduction. An algorithm for checking whether forgetting reduces information is given for a number of iterated belief revision operators: lexicographic, natural, severe, plain severe, moderate severe, restrained, very radical and full meet revisions. It may take exponential time in the worst case, which is expected given that the problem is coNP-hard, even in the Horn restriction. It is in coNP for homogeneous sequences of lexicographic revisions.