Using binary patterns for counting falsifying assignments of conjunctive forms

DOI10.1016/j.entcs.2015.06.003zbMath1351.68248OpenAlexW2233676586WikidataQ113317783 ScholiaQ113317783MaRDI QIDQ2520658

J. Raymundo Marcial-Romero, José A. Hernández, Pilar Pozos-Parra, Guillermo de Ita Luna

Publication date: 16 December 2016

Full work available at URL: https://doi.org/10.1016/j.entcs.2015.06.003

zbMATH Keywords

enumerative combinatoricsbinary patterns\#SAT\#FAL

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Logic in computer science (03B70)

Cites Work

• Unnamed Item
• Approximate inclusion-exclusion
• A bounded approximation for the minimum cost 2-sat problem
• Counting propositional models
• Inclusion-exclusion: exact and approximate
• Improved Bonferroni inequalities via abstract tubes. Inequalities and identities of inclusion-exclusion type
• Counting models for 2SAT and 3SAT formulae
• Counting the number of solutions for instances of satisfiability
• On the hardness of approximate reasoning
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

This page was built for publication: Using binary patterns for counting falsifying assignments of conjunctive forms