A CNF Class Generalizing Exact Linear Formulas

DOI10.1007/978-3-540-79719-7_22zbMath1138.68550MaRDI QIDQ3502711

Ewald Speckenmeyer, Stefan Porschen

Publication date: 27 May 2008

Published in: Theory and Applications of Satisfiability Testing – SAT 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79719-7_22

zbMATH Keywords

hypergraph; CNF satisfiability; exact linear formula; fibre-transversal

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

03B05: Classical propositional logic

Related Items

Linear CNF formulas and satisfiability, On Some SAT-Variants over Linear Formulas

Uses Software

• Ltur

Cites Work

• Unnamed Item
• Unnamed Item
• Nested satisfiability
• On finding solutions for extended Horn formulas
• A simplified NP-complete satisfiability problem
• Satisfiability of mixed Horn formulas
• Solving satisfiability in less than \(2^ n\) steps
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• 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
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Renaming a Set of Clauses as a Horn Set
• A CNF Formula Hierarchy over the Hypercube
• The complexity of satisfiability problems
• On Linear CNF Formulas