Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Answer Set Programming
Answer Sets
Dynamic Program
Linear Time
Subscribe
Academic
Publications
AnswerSet Programming with Bounded Treewidth
AnswerSet Programming with Bounded Treewidth,Michael Jakl,Reinhard Pichler,Stefan Woltran
Edit
AnswerSet Programming with Bounded Treewidth
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Michael Jakl
,
Reinhard Pichler
,
Stefan Woltran
In this paper, we present a novel approach to the evaluation of propositional answerset 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 oftheart systems.
Conference:
International Joint Conference on Artificial Intelligence  IJCAI
, pp. 816822, 2009
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.
(
ijcai.org
)
(
www.dbai.tuwien.ac.at
)
(
www.informatik.unitrier.de
)
Citation Context
(2)
...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 DPbased 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 Morak
,
et al.
A DynamicProgramming Based ASPSolver
...For other KR formalisms though such approaches already proved to be successful (see, e.g., [7,
14
])...
Reinhard Pichler
,
et al.
Belief Revision with Bounded Treewidth
References
(20)
A Tourist Guide through Treewidth
(
Citations: 306
)
Hans L. Bodlaender
Journal:
Acta Cybernetica  ACTAC
, vol. 11, no. 12, pp. 122, 1993
A LinearTime Algorithm for Finding TreeDecompositions of Small Treewidth
(
Citations: 618
)
Hans L. Bodlaender
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 25, no. 6, pp. 13051317, 1996
Conjunctive Query Containment Revisited
(
Citations: 131
)
Chandra Chekuri
,
Anand Rajaraman
Conference:
International Conference on Database Theory  ICDT
, pp. 5670, 1997
Graph Rewriting: An Algebraic and Logic Approach
(
Citations: 259
)
Bruno Courcelle
Published in 1990.
On the Computational Cost of Disjunctive Logic Programming: Propositional Case
(
Citations: 119
)
Thomas Eiter
,
Georg Gottlob
Journal:
Annals of Mathematics and Artificial Intelligence  AMAI
, vol. 15, no. 34, pp. 289323, 1995
Sort by:
Citations
(5)
Towards FixedParameter Tractable Algorithms for Argumentation
(
Citations: 1
)
Wolfgang Dvorák
,
Reinhard Pichler
,
Stefan Woltran
Conference:
Principles of Knowledge Representation and Reasoning  KR
, 2010
Monadic datalog over finite structures of bounded treewidth
(
Citations: 1
)
Georg Gottlob
,
Reinhard Pichler
,
Fang Wei
Journal:
ACM Transactions on Computational Logic  TOCL
, vol. 12, no. 1, pp. 148, 2010
A DynamicProgramming Based ASPSolver
Michael Morak
,
Reinhard Pichler
,
Stefan Rümmele
,
Stefan Woltran
Conference:
Logics in Artificial Intelligence  JELIA
, pp. 369372, 2010
Belief Revision with Bounded Treewidth
Reinhard Pichler
,
Stefan Rümmele
,
Stefan Woltran
Conference:
Logic Programming and Nonmonotonic Reasoning  LPNMR
, pp. 250263, 2009
Monadic datalog over finite structures with bounded treewidth
(
Citations: 6
)
Georg Gottlob
,
Reinhard Pichler
,
Fang Wei
Conference:
Symposium on Principles of Database Systems  PODS
, pp. 165174, 2007