Tractable answer-set programming with weight constraints: bounded treewidth is not enough

DOI10.1017/S1471068412000099zbMath1310.68053arXiv1204.3040MaRDI QIDQ5410728

Stefan Szeider, Stefan Woltran, Reinhard Pichler, Stefan Rümmele

Publication date: 17 April 2014

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.3040

zbMATH Keywords

treewidthanswer-set programmingparameterized complexity analysis

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic programming (68N17)

Related Items (5)

Complexity and approximability of parameterized MAX-CSPs ⋮ Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ New width parameters for SAT and \#SAT ⋮ A multiparametric view on answer set programming

Cites Work

• Unnamed Item
• Unnamed Item
• Safe separators for treewidth
• Safe reduction rules for weighted treewidth
• Treewidth. Computations and approximations
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Monadic second order logic on graphs with local cardinality constraints
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Tractable answer-set programming with weight constraints: bounded treewidth is not enough