A CNF Formula Hierarchy over the Hypercube

DOI10.1007/978-3-540-76928-6_25zbMath1138.68549OpenAlexW1594040910MaRDI QIDQ5385533

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

hypergraphtransversalsatisfiabilityhypercube formulavariable closure

Mathematics Subject Classification ID

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

Related Items (1)

A CNF Class Generalizing Exact Linear Formulas

Cites Work

• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Recognition of \(q\)-Horn formulae in linear time
• Polynomial-time inference of all valid implications for Horn and related formulae
• A perspective on certain polynomial-time solvable classes of satisfiability
• The complexity of theorem-proving procedures

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