Answer-Set Programming with Bounded Treewidth

Answer-Set Programming with Bounded Treewidth,Michael Jakl,Reinhard Pichler,Stefan Woltran

Answer-Set Programming with Bounded Treewidth   (Citations: 5)
BibTex | RIS | RefWorks Download
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 num- ber of answer sets in linear time and (ii) enumerat- ing all answer sets with linear delay. Our algorithm relies on dynamic programming. Therefore, our ap- proach significantly differs from standard ASP sys- tems 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, even a prototypical implementation is competitive compared to state- of-the-art systems.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...One such algorithm for disjunctive ASP has been presented recently [4]...
    • ...We refer to [4] also for details how concepts as incidence graphs, treewidth, tree decomposition, etc...
    • ...To evaluate this new DP-based approach for ASP, we have implemented two such methods: one for DLPs, cf. [4]; and another one applicable to HCFPs which relies on a rather different idea 1 . Thus, we call our solver dynASP, which first...

    Michael Moraket al. A Dynamic-Programming Based ASP-Solver

    • ...For other KR formalisms though such approaches already proved to be successful (see, e.g., [7,14])...

    Reinhard Pichleret al. Belief Revision with Bounded Treewidth

Sort by: