On Computational Aspects of Iterated Belief Change
| Autor: | Jean-Marie Lagniez, Pierre Marquis, Nicolas Schwind, Sébastien Konieczny |
|---|---|
| Přispěvatelé: | Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
010201 computation theory & mathematics
Iterated function Computer science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0102 computer and information sciences 02 engineering and technology Belief change 01 natural sciences Mathematical economics [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] |
| Zdroj: | Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20} Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence, Jul 2020, Yokohama, Japan. pp.1770-1776, ⟨10.24963/ijcai.2020/245⟩ IJCAI |
| DOI: | 10.24963/ijcai.2020/245⟩ |
| Popis: | International audience; Iterated belief change aims to determine how the belief state of a rational agent evolves given a sequence of change formulae. Several families of iterated belief change operators (revision operators, improvement operators) have been pointed out so far, and characterized from an axiomatic point of view. This paper focuses on the inference problem for iterated belief change, when belief states are represented as a special kind of stratified belief bases. The computational complexity of the inference problem is identified and shown to be identical for all revision operators satisfying Darwiche and Pearl's (R*1-R*6) postulates. In addition, some complexity bounds for the inference problem are provided for the family of soft improvement operators. We also show that a revised belief state can be computed in a reasonable time for large-sized instances using SAT-based algorithms, and we report empirical results showing the feasibility of iterated belief change for bases of significant sizes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|