Talks and Poster Presentations (with Proceedings-Entry):
R. Pichler, St. Rümmele, S. Woltran:
"Counting and Enumeration Problems with Bounded Treewidth";
Talk: Logic for Programming, Artificial Intelligence, and Reasoning (LPAR),
Dakar, Senegal;
04-25-2010
- 05-01-2010; in: "Lecture Notes in Artificial Intelligence 6355",
R. Goebel, J. Siekmann, W. Wahlster (ed.);
Lecture Notes in Computer Science,
6355
(2010),
ISBN: 978-3-642-17510-7;
387
- 404.
English abstract:
By Courcelle´s Theorem we know that any property of finite structures definable in monadic second-order logic (MSO) becomes tractable over structures with bounded treewidth. This result was extended to counting problems by Arnborg et al. and to enumeration problems by Flum et al. Despite the undisputed importance of these results for proving fixed-parameter tractability, they do not directly yield implementable algorithms. Recently, Gottlob et al. presented a new approach using monadic datalog to close the gap between theoretical tractability and practical computability for MSO-definable decision problems. In the current work we show how counting and enumeration problems can be tackled by an appropriate extension of the datalog approach.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-17511-4_22
Created from the Publication Database of the Vienna University of Technology.