Complexity results for answer set programming with bounded predicate arities and implications
From MaRDI portal
Publication:2426101
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic programming (68N17)
Related Items (18)
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
Cites Work
- 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
- 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
This page was built for publication: Complexity results for answer set programming with bounded predicate arities and implications
