On the counting complexity of propositional circumscription

DOI10.1016/J.IPL.2007.11.006zbMATH Open1186.68448OpenAlexW2019722250MaRDI QIDQ963360FDOQ963360

Authors: Arnaud Durand, Miki Hermann 

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.11.006

Recommendations

• A dichotomy in the complexity of propositional circumscription
• Logic for Programming, Artificial Intelligence, and Reasoning
• scientific article; zbMATH DE number 1884382
• scientific article; zbMATH DE number 1962835
• Some computational aspects of circumscription

zbMATH Keywords

computational complexitycounting complexityHornand affine formulasbijunctivedual HornHypergraph transversalpropositional circumscription

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)

Cites Work

• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• Minimal vectors in linear codes
• The complexity of satisfiability problems
• Generating all maximal models of a Boolean expression
• Title not available (Why is that?)
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Subtractive reductions and complete problems for counting complexity classes
• The polynomial-time hierarchy
• The complexity of model checking for circumscriptive formulae
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Circumscription - a form of non-monotonic reasoning
• Handbook of automated reasoning. In 2 vols
• Complete sets and the polynomial-time hierarchy
• The complexity of minimal satisfiability problems

Cited In (10)

• Title not available (Why is that?)
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• On compact representations of propositional circumscription
• Logic for Programming, Artificial Intelligence, and Reasoning
• Some computational aspects of circumscription
• Counting constraint satisfaction problems
• Counting complexity of propositional abduction
• Counting minimal transversals of \(\beta\)-acyclic hypergraphs
• Counting minimal dominating sets
• The Complexity of Circumscriptive Inference in Post’s Lattice

This page was built for publication: On the counting complexity of propositional circumscription

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