Complexity results for answer set programming with bounded predicate arities and implications

DOI10.1007/s10472-008-9086-5zbMath1138.68017OpenAlexW2157334516MaRDI QIDQ2426101

Thomas Eiter, Stefan Woltran, Wolfgang Faber, Michael Fink

Publication date: 21 April 2008

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-008-9086-5

zbMATH Keywords

Computational complexityAnswer set programming

Mathematics Subject Classification ID

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

Related Items

Linking Open-World Knowledge Bases Using Nonmonotonic Rules, Reasoning with Forest Logic Programs and f-hybrid knowledge bases, Inconsistency Management for Traffic Regulations: Formalization and Complexity Results, LARS: a logic-based framework for analytic reasoning over streams, Unnamed Item, The power of non-ground rules in Answer Set Programming, Complexity results for answer set programming with bounded predicate arities and implications, Extended RDF: computability and complexity issues, The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference, Unnamed Item, Unnamed Item, Why-provenance information for RDF, rules, and negation, Solving Advanced Argumentation Problems with Answer Set Programming, selp: A Single-Shot Epistemic Logic Program Solver, Pruning external minimality checking for answer set programs using semantic dependencies, Abstraction for non-ground answer set programs, Complexity results for probabilistic answer set programming, Answer Set Programming: A Primer

Uses Software

• Gringo
• Lparse
• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong order equivalence
• Magic Sets and their application to data integration
• Computing only minimal answers in disjunctive deductive databases
• Reasoning with minimal models: efficient algorithms and applications
• An extension to linear resolution with selection function
• Expressive power and complexity of partial models for disjunctive deductive databases
• Succinctness as a source of complexity in logical formalisms
• Duality for goal-driven query processing in disjunctive deductive databases
• SLT-resolution for the well-founded semantics
• Answer set programming and plan generation
• The expressive powers of the logic programming semantics
• On the computational cost of disjunctive logic programming: Propositional case
• Propositional semantics for disjunctive logic programs
• Logic programs with stable model semantics as a constraint programming paradigm
• Complexity results for answer set programming with bounded predicate arities and implications
• Bottom-up computation of perfect models for disjunctive theories
• The complexity of acyclic conjunctive queries
• A fixpoint semantics for disjunctive logic programs
• Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications
• Autoepistemic logic
• Model generation and state generation for disjunctive logic programs
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Computing preferred answer sets by meta-interpretation in Answer Set Programming
• On the expressibility of stable logic programming
• Strong equivalence made easy: nested expressions and weight constraints
• Logic Programming
• Strongly equivalent logic programs
• Resolution for skeptical stable model semantics