Complexity results for answer set programming with bounded predicate arities and implications
From MaRDI portal
Publication:2426101
DOI10.1007/s10472-008-9086-5zbMath1138.68017MaRDI QIDQ2426101
Thomas Eiter, Michael Fink, Stefan Woltran, Wolfgang Faber
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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68N17: Logic programming
Related Items
Uses Software
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
