Using Binary Patterns for Counting Falsifying Assignments of Conjunctive Forms | Zendy

Guillermo De Ita Luna | Zendy; J. Raymundo MarcialRomero | Zendy; Pilar Pozos-Parra | Zendy; José Antonio Hernández Servín | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Using Binary Patterns for Counting Falsifying Assignments of Conjunctive Forms

Author(s) -

Guillermo De Ita Luna,

J. Raymundo MarcialRomero,

Pilar Pozos-Parra,

José Antonio Hernández Servín

Publication year - 2015

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2015.06.003

Subject(s) - binary number , mathematics , set (abstract data type) , combinatorics , representation (politics) , conjunctive normal form , discrete mathematics , space (punctuation) , computer science , arithmetic , law , politics , political science , programming language , operating system

The representation of the set of falsifying assignments of clauses via binary patterns has been useful in the design of algorithms for solving #FAL (counting the number of falsifying assignments of conjunctive forms (CF)). Given as input a CF formula F expressed by m clauses defined over n variables, we present a deterministic algorithm for computing #FAL(F). Principally, our algorithm computes non-intersecting subsets of falsifying assignments of F until the space of falsifying assignments defined by F is covered. Due to #SAT(F) = 2n-#FAL(F), results about #FAL can be established dually for #SAT. The time complexity of our proposals for computing #FAL(F) is established according to the number of clauses and the number of variables of F

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research