Answer-Set Programming with Bounded Treewidth
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 816-821.
Abstract
In this paper, we present a novel approach to the evaluation of propositional answer-set programs. In particular, for programs with bounded treewidth, our algorithm is capable of (i) computing the number of answer sets in linear time and (ii) enumerating all answer sets with linear delay. Our algorithm relies on dynamic programming, which so far has not been applied to ASP-problems. Therefore, our approach significantly differs from standard ASP-systems which implement techniques stemming from SAT or CSP, and thus usually do not exploit fixed parameter properties of the programs. We provide first experimental results which underline that, for programs with low treewidth, already a prototypical implementation is competitive compared to state-of-the-art systems.Michael Jakl, Reinhard Pichler, Stefan Woltran
@inproceedings{ijcai2009p140,
title = {Answer-Set Programming with Bounded Treewidth},
author = {Jakl, Michael and Pichler, Reinhard and Woltran, Stefan},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {816--821},
year = {2009},
url = {https://ijcai.org/proceedings/2009/140},
}
TY - CPAPER TI - Answer-Set Programming with Bounded Treewidth AU - Jakl, Michael AU - Pichler, Reinhard AU - Woltran, Stefan T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 816 EP - 821 UR - https://ijcai.org/proceedings/2009/140 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
