On the Parameterized Complexity of Belief Revision

Pfandler, Andreas; Rümmele, Stefan; Wallner, Johannes Peter; Woltran, Stefan

On the Parameterized Complexity of Belief Revision

Andreas Pfandler, Stefan Rümmele, Johannes Peter Wallner, Stefan Woltran

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 3149-3154.

Abstract

Parameterized complexity is a well recognized vehicle for understanding the multitude of complexity AI problems typically exhibit. However, the prominent problem of belief revision has not undergone a systematic investigation in this direction yet. This is somewhat surprising, since by its very nature of involving a knowledge base and a revision formula, this problem provides a perfect playground for investigating novel parameters. Among our results on the parameterized complexity of revision is thus a versatile fpt algorithm which is based on the parameter of the number of atoms shared by the knowledge base and the revision formula. Towards identifying the frontier between parameterized tractability and intractability, we also give hardness results for classes such as co-W[1], para-Theta2P and FPTNP[f(k)]

Andreas Pfandler, Stefan Rümmele, Johannes Peter Wallner, and Stefan Woltran. 2015. On the Parameterized Complexity of Belief Revision. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 3149–3154. https://ijcai.org/proceedings/2015/444

@inproceedings{ijcai2015p444,
  title     = {On the Parameterized Complexity of Belief Revision},
  author    = {Pfandler, Andreas and Rümmele, Stefan and Wallner, Johannes Peter and Woltran, Stefan},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {3149--3154},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Knowledge Representation and Reasoning},
  url       = {https://ijcai.org/proceedings/2015/444},
}

TY  - CPAPER
TI  - On the Parameterized Complexity of Belief Revision
AU  - Pfandler, Andreas
AU  - Rümmele, Stefan
AU  - Wallner, Johannes Peter
AU  - Woltran, Stefan
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 3149
EP  - 3154
UR  - https://ijcai.org/proceedings/2015/444
ER  -