研究信念更新中遗忘的复杂性，发现部分情况可高效处理。
Forgetting in short and heterogeneous sequences of belief revisions
- 针对两类信念更新序列设计了判断遗忘是否有效的算法
- 两步词典序霍恩更新可在多项式时间内解决
- 适用于需分析信念系统变化的研究者
遗忘特定信念更新事件可能不会导致信息丢失，因为其他更新可能包含或蕴含相同信息。对于任意两个词典序更新序列或任意长的词典序霍恩更新序列，判断遗忘是否有效已被证明为 coNP-hard。本文提出一个多项式时间算法，适用于两步词典序霍恩更新情形。对于包含非词典序更新的异构序列，其复杂性被证明属于 Delta2。此前已知的 coNP-hardness 进一步强化为 Dp-hardness。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。