Using binary patterns for counting falsifying assignments of conjunctive forms

DOI10.1016/J.ENTCS.2015.06.003MaRDI QIDQ2520658zbMATH OpenOpenAlexWikidataFDO

Authors J. Raymundo Marcial-Romero, Pilar Pozos-Parra, José Hernández, 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)

Recommendations

• Counting truth assignments of formulas of bounded tree-width or clique-width
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• scientific article; zbMATH DE number 746893
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Decomposing quantified conjunctive (or disjunctive) formulas
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• Reconstruction of Boolean formulas in conjunctive normal form

Cites work

• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• A bounded approximation for the minimum cost 2-sat problem
• A threshold for a polynomial solution of \#2SAT
• Approximate inclusion-exclusion
• Counting models for 2SAT and 3SAT formulae
• Counting propositional models
• Counting the number of solutions for instances of satisfiability
• Improved Bonferroni inequalities via abstract tubes. Inequalities and identities of inclusion-exclusion type
• Inclusion-exclusion: exact and approximate
• On the hardness of approximate reasoning
• The complexity of counting in sparse, regular, and planar graphs

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

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