A CNF Formula Hierarchy over the Hypercube

DOI10.1007/978-3-540-76928-6_25MaRDI QIDQ5385533zbMATH OpenOpenAlexFDO

Authors Stefan Porschen

Publication date 6 May 2008

Published in AI 2007: Advances in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-76928-6_25

zbMATH Keywords

hypercube formulahypergraphsatisfiabilitytransversalvariable closure

Mathematics Subject Classification ID

Classical propositional logic (03B05) Hypergraphs (05C65) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A CNF Class Generalizing Exact Linear Formulas
• Theory and Applications of Satisfiability Testing
• On extremal k-CNF formulas
• On extremal \(k\)-CNF formulas
• On Linear CNF Formulas
• Satisfiability of acyclic and almost acyclic CNF formulas
• Satisfiability of acyclic and almost acyclic CNF formulas
• CNF satisfiability in a subspace and related problems
• Linear CNF formulas and satisfiability
• Exact satisfiability of linear CNF formulas

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A perspective on certain polynomial-time solvable classes of satisfiability
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Polynomial-time inference of all valid implications for Horn and related formulae
• Recognition of q-Horn formulae in linear time
• Solving satisfiability in less than \(2^ n\) steps
• The complexity of theorem-proving procedures

Cited in

(1)

• A CNF Class Generalizing Exact Linear Formulas

This page was built for publication: A CNF Formula Hierarchy over the Hypercube

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