On the query complexity of selecting minimal sets for monotone predicates

DOI10.1016/J.ARTINT.2016.01.002MaRDI QIDQ253999zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Mikoláš Janota, Joao Marques-Silva

Publication date 8 March 2016

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2016.01.002

zbMATH Keywords

backboneindependent variablesminimal correction setminimal setminimal unsatisfiable setmonotone predicatesquery complexitySAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Minimal sets on propositional formulae. Problems and reductions
• Algorithms for computing backbones of propositional formulae
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
• The complexity of minimal satisfiability problems
• On exact selection of minimally unsatisfiable subformulae

Cites work

• A taxonomy of complexity classes of functions
• Algorithms for computing backbones of propositional formulae
• Algorithms for computing minimal unsatisfiable subsets of constraints
• Axiom Pinpointing in General Tableaux
• Computational Complexity
• Consequence finding algorithms
• Consistent subsets of inconsistent systems: structure and behaviour
• Fixed-parameter tractable reductions to SAT
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1072533 (Why is no real title available?)
• scientific article; zbMATH DE number 1946872 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• Minimal sets on propositional formulae. Problems and reductions
• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• On truth-table reducibility to SAT
• Oracles That Compute Values
• Property-directed incremental invariant generation
• Removing redundancy from a clause
• The complexity of facets resolved
• The complexity of optimization problems
• The complexity of selecting maximal solutions
• The complexity of some subclasses of minimal unsatisfiable formulas.
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints

Cited in

(14)

• Minimal sets on propositional formulae. Problems and reductions
• Paracoherent answer set computation
• Determining inference semantics for disjunctive logic programs
• MCS Extraction with Sublinear Oracle Queries
• Efficient reasoning for inconsistent Horn formulae
• Cautious reasoning in ASP via minimal models and unsatisfiable cores
• Omission-based abstraction for answer set programs
• Better paracoherent answer sets with less resources
• Witnesses for Answer Sets of Logic Programs
• Computing generating sets of minimal size in finite algebras
• Contrastive explanations for answer-set programs
• Boosting definability bipartition computation using SAT witnesses
• Algorithms for computing the set of acceptable arguments
• Counting minimal unsatisfiable subsets

This page was built for publication: On the query complexity of selecting minimal sets for monotone predicates

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