A CNF Class Generalizing Exact Linear Formulas

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

Stefan Porschen, Ewald Speckenmeyer

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

hypergraphCNF satisfiabilityexact linear formulafibre-transversal

Mathematics Subject Classification ID

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

Related Items (2)

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

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

This page was built for publication: A CNF Class Generalizing Exact Linear Formulas