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

DOI10.1017/S1471068410000463MaRDI QIDQ2884255zbMATH OpenFDO

Authors Mirosław Truszczyński

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)

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

Cites work

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

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
• Complexity-sensitive decision procedures for abstract argumentation
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• 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)