# US 2013/0159241 A1 · Template clauses based sat techniques

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0159241 A1
- Document ID: US20130159241A1
- Status: Published application
- Kind: A1
- Application number: 13/766,784
- Filed: 2013-02-14
- Published: 2013-06-20
- Earliest claimed: 2010-01-19
- Assignees: International Business Machines Corporation
- Inventors: Oded Fuhrmann; Ohad Shacham
- Web page: https://patentgrep.com/patent/US20130159241A1

## CPC

- G06N 5/048: Fuzzy inferencing
- G06N 5/04: Inference or reasoning models
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A CNF formula comprises at least one template clause representing a set of concrete clauses, each associated with a different temporal shift. The template clause is utilized by a SAT solver in determining satisfiability of the CNF formula. The template clause may be utilized to reduce amount of storage resources required for performing the satisfiability analysis. The template clause may in some cases increase feasibility of determining satisfiability. The template clause may in some cases reduce required time to determine satisfiability. The template clause may be utilized in incremental SAT solving to reuse deduced relations between literals that are applicable to additional cycles, such as invariants originating from a transition relation of a model.

## Claims

### Claim at position 1

-22. (canceled)

### Claim 23

A SAT solving apparatus having a processor, the SAT solving apparatus comprising:
a receiver configured to receive a template SAT problem associated with a model that is modeled checked, the template SAT problem comprises a plurality of clauses and a template clause, the template clause represents a plurality of concrete clauses each associated with a different temporal shift, the template clause is associated with a literal; and
a literal value determinator configured to determine a value of the literal in a cycle based on the template clause and a temporal shift, said literal value determinator comprising:
a temporal shifter configured to determine a concrete clause of the plurality of concrete clauses based on the template clause and the temporal shift;
a clauses deducer configured to determine a deduced clause, said clauses deducer is configured to utilize said literal value determinator;
wherein said SAT solving apparatus is configured to deduce a solution to the template SAT problem, the solution is selected from the group consisting of a satisfying assignment and a proof of unsatisfiability.

### Claim 24 (depends on 23)

The SAT solving apparatus of claim 23 further comprising:
a clauses repository configured to retain the plurality of clauses and the deducted clause; and
an incremental module configured to reuse a portion of the clauses of said clauses repository in response to said receiver receiving a second template SAT problem, the second template SAT problem is associated with the template SAT problem.

### Claim 25 (depends on 23)

The SAT solving apparatus of claim 23, wherein the model is a bounded model.

### Claim 26 (depends on 23)

The SAT solving apparatus of claim 23, wherein the template clause represents an invariant applicable to each cycle of the model checking problem.

### Claim 27 (depends on 3)

The SAT solving apparatus of claim 3 further comprising a monitoring module responsive to a modification of a value of a second literal associated with a clause.

### Claim 28 (depends on 3)

The SAT solving apparatus of claim 3 further comprising a monitoring module responsive to a modification of a value of a second literal associated with the template clause in respect to a first temporal shift; and wherein said monitoring module is further responsive to a modification of a value of a third literal associated with the template clause in respect to a second temporal shift.

### Claim 29

A method to solve a template SAT problem associated with a model that is modeled checked, said method is performed by a computerized device, said method comprising:
receiving the template SAT problem, the template SAT problem comprising a plurality of clauses and a template clause, the template clause represents a plurality of concrete clauses each associated with a different temporal shift, the template clause is associated with a literal;
determining a value of the literal in a cycle based on the template clause and a temporal shift, said determining the value of the literal comprises:
determining a concrete clause of the plurality of concrete clauses based on the template clause and the temporal shift; and
determining a deduced clause based on at least the value of the literal in the cycle;
deducing a solution to the template SAT problem, the solution is selected from the group consisting of a satisfying assignment and a proof of unsatisfiability; and
outputting the solution.

### Claim 30 (depends on 29)

The method of claim 29, wherein the model is a bounded model.

### Claim 31 (depends on 29)

The method of claim 29 further comprising:
retaining the deduced clause in a storage device of the computerized device; and
retaining the plurality of clauses in the storage device.

### Claim 32 (depends on 29)

The method of claim 29 further comprising:
receiving a second template SAT problem, the second template SAT problem is associated with the template SAT problem; and
deducing a solution to the second template SAT problem based on the deduced clause.

### Claim 33 (depends on 29)

The method of claim 29 further comprising:
determining a value of the literal based on the template clause in respect to at least two cycles; and
revoking determination of said determining a value of the literal.

### Claim 34

A computer program product comprising a non-transitory computer readable medium retaining program instructions, which instructions when read by a processor, cause the processor to perform the steps of:
receiving the template SAT problem, the template SAT problem comprising a plurality of clauses and a template clause, the template clause represents a plurality of concrete clauses each associated with a different temporal shift, the template clause is associated with a literal;
determining a value of the literal in a cycle based on the template clause and a temporal shift, said determining the value of the literal comprises:
determining a concrete clause of the plurality of concrete clauses based on the template clause and the temporal shift; and
determining a deduced clause based on at least the value of the literal in the cycle; and
deducing a solution to the template SAT problem, the solution is selected from the group consisting of a satisfying assignment and a proof of unsatisfiability.

### Claim 35 (depends on 34)

The computer program product of claim 34, wherein the instructions, when read by a processor, further cause the processor to output the solution.

### Claim 36 (depends on 34)

The computer program product of claim 34, wherein the model is a bounded model.

### Claim 37 (depends on 34)

The computer program product of claim 34, wherein the instructions, when read by a processor, further cause the processor to:
receive a second template SAT problem, the second template SAT problem is associated with the template SAT problem; and
deduce a solution to the second template SAT problem based on the deduced clause.

### Claim 38 (depends on 34)

The computer program product of claim 34, wherein the instructions, when read by a processor, further cause the processor to:
determine a value of the literal based on the template clause in respect to at least two cycles; and
revoke determination of said determining a value of the literal.
