39 results about "Conjunctive normal form" patented technology

An improved normalization methodology enabling better optimization of SQL queries is described. The normalization methodology effectively handles three-valued SQL search conditions and operates in reduced memory environments. A query is examined and selectively normalized by examining each segment of the query to determine whether it is advantageous to fully convert that segment to conjunctive normal form (CNF). If full conversion of the segment to CNF is not advantageous, then only the useful conjunctive conditions (prime implicates) that can be derived from the original input are saved. These useful conjuncts (prime implicates) are unioned with the original statement, resulting in a search condition that is semantically equivalent to the original expression, but that can be better exploited by a query optimizer. This enables better optimization of the original query without the system overhead that would result from full normalization of the query.

A method for Boolean Satisfiability (SAT). The method comprises using a variable decision heuristic in a SAT algorithm and pruning the search space of SAT using said decision heuristic. The decision heuristic is based on partitioning a conjunctive normal form (CNF) of a Boolean formula corresponding to the SAT and the partitioning is induced by a separator set. An image computaion method that uses the disclosed method for solving the SAT.

This disclosure teaches a method of Boolean satisfiability checking (SAT) for a circuit. The method comprises identifying inactive clauses in the conjunctive normal form (CNF) of the circuit and removing the inactive clauses from the CNF.

Provided is a totally new formal verification algorithm aiming at an arithmetic circuit. One example embodiment provides a new formal method which couples (combines) a satisfiability (SAT) solver and a unique Reverse Engineering (RE) method which makes use the arithmetic logical circuit structure properties (e.g. 1-bit adder structure, Carry tree structure) to achieve the algorithm for arithmetic circuits regardless of its size. The example embodiment provides basic through of how to optimize the operational complexity of a conventional arithmetic circuit verification method. The basic through is shown as followed: assuming that there are two arithmetic circuits f and g; conducting equivalence checking of the two arithmetic circuits by firstly generating a conjunctive normal form (CNF) encoding; and determining whether the encoding of the two arithmetic circuits is equal through a satisfiability (SAT) tool. If the structural difference between f and g is minimized as far as possible before generating a conjunctive normal form (CNF) encoding, the arithmetic circuit verification is completed in polynomial time rather than in exponential time.

A method for analyzing system-problems, comprising the steps of: accepting from a user an input describing a system having a problem; parsing the user input to create a boolean representation of the system, the boolean representation comprising a series of equations; determining that the boolean representation comprises an unsatisfiable series of equations; for each equation in the series of equations, performing the steps of: creating a modified series of equations by removing the equation from the series of equations; and determining if the modified series of equations is satisfiable, and, if the modified series of equations is satisfiable, deriving a solution wording from the removed equation.

A processor including a Boolean logic unit, wherein the Boolean logic unit is operable for performing the short-circuit evaluation of Conjunctive Normal Form Boolean expressions / operations, a plurality of input / output interfaces, wherein the plurality of input / output interfaces are operable for receiving a plurality of compiled Boolean expressions / operations and transmitting a plurality of compiled results, and a plurality of registers. An associated processing method including starting an operation related to a Conjunctive Normal Form Boolean expression, wherein the Boolean expression comprises a conjunct, evaluating the conjunct, and selectively short-circuiting a portion of the Boolean expression.

The invention discloses a constraint-based system fault injecting method. The method comprises the steps of: classifying constraints into atomic condition and conjunction normal form clause levels according to atomic condition inversion and the conjunction normal form clause inversion strategies and solving a group of negative forms of the specification constraints at the levels to serve as basesof generating fault data; replacing constraint variables in the inverted constraints with normal input combinations, gradually carrying out slack replacement on the constraint variables and finding minimum-variation fault data which have the least number of slack variables and are closest to a real situation through a constraint solving operation; carrying out faulty injection on a to-be-tested system by taking the minimum-variation fault data as test inputs to obtain fault injecting results. The method disclosed by the invention has the beneficial effects that by adopting a new fault injecting technology, the more real and more sufficient fault data are generated; the error detecting capability of the fault injection is strengthened; and faults close to the normal state are also beneficial for a tester to repair and eliminate the defects at the same time.