On Some SAT-Variants over Linear Formulas

DOI10.1007/978-3-540-95891-8_41MaRDI QIDQ3599093zbMATH OpenOpenAlexFDO

Authors Stefan Porschen, Tatjana Schmidt

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-95891-8_41

zbMATH Keywords

linear hypergraphexact satisfiabilitylinear formulabicolorabilitynot-all-equal satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• XSAT and NAE-SAT of linear CNF classes
• Complexity Results for Linear XSAT-Problems
• On Linear CNF Formulas
• Theory and Applications of Satisfiability Testing
• Linear CNF formulas and satisfiability

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3803174 (Why is no real title available?)
• A CNF Class Generalizing Exact Linear Formulas
• A short proof of Fisher's inequality
• Axioms and hulls
• Linear CNF formulas and satisfiability
• New algorithms for exact satisfiability
• The Non-Existence of Finite Projective Planes of Order 10
• The complexity of satisfiability problems

Cited in

(15)

• A CNF Class Generalizing Exact Linear Formulas
• scientific article; zbMATH DE number 1979549 (Why is no real title available?)
• Exact satisfiability of linear CNF formulas
• Satisfiability with index dependency
• XSAT and NAE-SAT of linear CNF classes
• Theory and Applications of Satisfiability Testing
• On Linear CNF Formulas
• Linear CNF formulas and satisfiability
• Linear templates of ACTL formulas with an application to SAT-based verification
• Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
• SAT-Problems and Reductions with Respect to the Number of Variables
• Satisfiable formulas closed under replacement
• Variant-Based Satisfiability in Initial Algebras
• About some UP-based polynomial fragments of SAT
• Satisfiability with index dependency

This page was built for publication: On Some SAT-Variants over Linear Formulas

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