Forgetting in short and heterogeneous sequences of belief revisions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913840884613120 |
|---|---|
| author | Liberatore, Paolo |
| author_facet | Liberatore, Paolo |
| contents | Forgetting a specific belief revision episode may not erase information because the other revisions may provide or entail the same information. Whether it does was proved coNP-hard for sequences of two arbitrary lexicographic revisions or arbitrarily long lexicographic Horn revisions. A polynomial algorithm is presented for the case of two lexicographic Horn revision. Heterogeneous sequences, including revisions other than lexicographic, were proved to belong in Delta2. Their previously proved coNP-hardness is enhanced to Dp-hardness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_13986 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Forgetting in short and heterogeneous sequences of belief revisions Liberatore, Paolo Computational Complexity Artificial Intelligence Forgetting a specific belief revision episode may not erase information because the other revisions may provide or entail the same information. Whether it does was proved coNP-hard for sequences of two arbitrary lexicographic revisions or arbitrarily long lexicographic Horn revisions. A polynomial algorithm is presented for the case of two lexicographic Horn revision. Heterogeneous sequences, including revisions other than lexicographic, were proved to belong in Delta2. Their previously proved coNP-hardness is enhanced to Dp-hardness. |
| title | Forgetting in short and heterogeneous sequences of belief revisions |
| topic | Computational Complexity Artificial Intelligence |
| url | https://arxiv.org/abs/2504.13986 |