A CNF Class Generalizing Exact Linear Formulas

DOI10.1007/978-3-540-79719-7_22MaRDI QIDQ3502711zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On Linear CNF Formulas
• On Some SAT-Variants over Linear Formulas
• Linear CNF formulas and satisfiability
• XSAT and NAE-SAT of linear CNF classes
• Exact satisfiability of linear CNF formulas

Cites work

• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• A CNF Formula Hierarchy over the Hypercube
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A perspective on certain polynomial-time solvable classes of satisfiability
• A simplified NP-complete satisfiability problem
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Nested satisfiability
• On Linear CNF Formulas
• On finding solutions for extended Horn formulas
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Polynomial-time inference of all valid implications for Horn and related formulae
• Recognition of q-Horn formulae in linear time
• Renaming a Set of Clauses as a Horn Set
• Satisfiability of mixed Horn formulas
• Solving satisfiability in less than \(2^ n\) steps
• The complexity of satisfiability problems

Cited in

(6)

• scientific article; zbMATH DE number 5613969 (Why is no real title available?)
• A linear-time transformation of linear inequalities into conjunctive normal form
• Linear CNF formulas and satisfiability
• On Some SAT-Variants over Linear Formulas
• A CNF Formula Hierarchy over the Hypercube
• On extremal \(k\)-CNF formulas

Describes a project that uses

Uses Software

• Ltur

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

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