Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs

DOI10.1017/S1471068410000463zbMATH Open1242.68052MaRDI QIDQ2884255FDOQ2884255

Authors: Mirosław Truszczyński 

Publication date: 24 May 2012

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

Recommendations

• Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs
• On the computational cost of disjunctive logic programming: Propositional case
• Stability, supportedness, minimality and Kleene answer set programs
• Determining inference semantics for disjunctive logic programs
• Complexity of computing with extended propositional logic programs

zbMATH Keywords

supported modelsanswer setscomplexity of reasoning

Mathematics Subject Classification ID

Logic programming (68N17)

Cites Work

• On the computational cost of disjunctive logic programming: Propositional case
• Propositional semantics for disjunctive logic programs
• Complexity classifications of Boolean constraint satisfaction problems
• Classifying the Complexity of Constraints Using Finite Algebras
• Autoepistemic logic
• The complexity of model checking for circumscriptive formulae
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• The complexity of propositional closed world reasoning and circumscription
• The relationship between stable, supported, default and autoepistemic semantics for general logic programs
• Negation as failure in the head
• Characterizations of the disjunctive stable semantics by partial evaluation
• Complexity of Default Logic on Generalized Conjunctive Queries
• What makes propositional abduction tractable
• Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs

Cited In (10)

• IASCAR: incremental answer set counting by anytime refinement
• Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs
• Logic for Programming, Artificial Intelligence, and Reasoning
• A multiparametric view on answer set programming
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• Complexity-sensitive decision procedures for abstract argumentation
• Inconsistency proofs for ASP: the ASP-DRUPE format
• Backdoors to tractable answer set programming
• Backdoors to normality for disjunctive logic programs
• Dual-normal logic programs -- the forgotten class

This page was built for publication: Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884255)