Complexity results for answer set programming with bounded predicate arities and implications
From MaRDI portal
Publication:2426101
DOI10.1007/S10472-008-9086-5zbMATH Open1138.68017OpenAlexW2157334516MaRDI QIDQ2426101FDOQ2426101
Authors: Thomas Eiter, Wolfgang Faber, Michael Fink, Stefan Woltran 
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
Recommendations
- On the Complexity of Answer Set Programming with Aggregates
- The power of non-ground rules in Answer Set Programming
- An Introduction to Answer Set Programming and Some of Its Extensions
- Complexity of Rule Redundancy in Non-ground Answer-Set Programming over Finite Domains
- Answer set programming based on propositional satisfiability
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic programming (68N17)
Cites Work
- On the computational cost of disjunctive logic programming: Propositional case
- Propositional semantics for disjunctive logic programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Knowledge Representation, Reasoning and Declarative Problem Solving
- Strong equivalence made easy: nested expressions and weight constraints
- Title not available (Why is that?)
- Strongly equivalent logic programs
- Magic Sets and their application to data integration
- Title not available (Why is that?)
- Reasoning with minimal models: efficient algorithms and applications
- Answer set programming and plan generation
- Logic programs with stable model semantics as a constraint programming paradigm
- Title not available (Why is that?)
- Autoepistemic logic
- Title not available (Why is that?)
- The complexity of acyclic conjunctive queries
- Logic Programming
- Succinctness as a source of complexity in logical formalisms
- Computing preferred answer sets by meta-interpretation in Answer Set Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fixpoint semantics for disjunctive logic programs
- The expressive powers of the logic programming semantics
- SLT-resolution for the well-founded semantics
- Duality for goal-driven query processing in disjunctive deductive databases
- Bottom-up computation of perfect models for disjunctive theories
- Resolution for skeptical stable model semantics
- Strong order equivalence
- Title not available (Why is that?)
- Complexity results for answer set programming with bounded predicate arities and implications
- On the expressibility of stable logic programming
- Computing only minimal answers in disjunctive deductive databases
- Title not available (Why is that?)
- Title not available (Why is that?)
- An extension to linear resolution with selection function
- Expressive power and complexity of partial models for disjunctive deductive databases
- Title not available (Why is that?)
- Model generation and state generation for disjunctive logic programs
- Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications
Cited In (24)
- Title not available (Why is that?)
- Linking Open-World Knowledge Bases Using Nonmonotonic Rules
- Complexity of Rule Redundancy in Non-ground Answer-Set Programming over Finite Domains
- Answer Set Programming: A Primer
- Semantical characterizations and complexity of equivalences in answer set programming
- The power of non-ground rules in Answer Set Programming
- Abstraction for non-ground answer set programs
- LARS: a logic-based framework for analytic reasoning over streams
- Signed dual tableaux for Kleene answer set programs
- Why-provenance information for RDF, rules, and negation
- Reasoning with Forest Logic Programs and f-hybrid knowledge bases
- On the Complexity of Answer Set Programming with Aggregates
- selp: A Single-Shot Epistemic Logic Program Solver
- Title not available (Why is that?)
- Pruning external minimality checking for answer set programs using semantic dependencies
- Answer set solving with bounded treewidth revisited
- Title not available (Why is that?)
- Solving Advanced Argumentation Problems with Answer Set Programming
- The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference
- Extended RDF: computability and complexity issues
- Inconsistency management for traffic regulations: formalization and complexity results
- Complexity results for probabilistic answer set programming
- Complexity results for answer set programming with bounded predicate arities and implications
- The Complexity Boundary of Answer Set Programming with Generalized Atoms under the FLP Semantics
Uses Software
This page was built for publication: Complexity results for answer set programming with bounded predicate arities and implications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2426101)
