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

DOI10.1017/S1471068410000463zbMath1242.68052MaRDI QIDQ2884255

Miroslaw Truszczynski

Publication date: 24 May 2012

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

zbMATH Keywords

supported modelsanswer setscomplexity of reasoning

Mathematics Subject Classification ID

Logic programming (68N17)

Related Items

Backdoors to Normality for Disjunctive Logic Programs ⋮ Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Dual-normal logic programs – the forgotten class ⋮ Inconsistency Proofs for ASP: The ASP - DRUPE Format ⋮ Complexity-sensitive decision procedures for abstract argumentation ⋮ A multiparametric view on answer set programming ⋮ Backdoors to tractable answer set programming

Cites Work

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