# US 2008/0307372 A1 · Method and system for performing minimization of input count during structural netlist overapproximation

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

- Number: US 2008/0307372 A1
- Document ID: US20080307372A1
- Status: Published application
- Kind: A1
- Application number: 12/047,361
- Filed: 2008-03-13
- Published: 2008-12-11
- Earliest claimed: 2005-09-13
- Assignees: International Business Machines Corporation
- Inventors: JASON R. BAUMGARTNER; Robert L. Kanzelman; Hari Mony; Viresh Paruthi
- Web page: https://patentgrep.com/patent/US20080307372A1

## CPC

- G06F 30/3323: using formal methods, e.g. equivalence checking or property checking
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for performing verification is disclosed. The method includes selecting a set of gates to add to a first localization netlist and forming a refinement netlist. A min-cut is computed with sinks having one or more gates in the refinement netlist and sources comprising one or more inputs of an original netlist and one or more registers registers of the original netlist which are not part of the refinement netlist. A final localized netlist is obtained by adding one or more gates to the refinement netlist to grow the refinement netlist until reaching one or more cut-gates of the min-cut.

## Claims

### Claim 1

A system for performing verification, said system comprising:
means for selecting a set of gates to add to a first localization netlist;
means for forming a refinement netlist;
means for computing a min-cut with sinks comprising one or more gates in said refinement netlist and sources comprising one or more inputs of an original netlist and one or more registers of said original netlist which are not part of said refinement netlist; and
means for obtaining a final localized netlist by adding one or more gates to said refinement netlist to grow said refinement netlist until reaching one or more cut-gates of said min-cut.

### Claim 2 (depends on 1)

The system of claim 1, wherein said means for forming said refinement netlist further comprises means for forming said refinement netlist by adding said first localization netlist and said set of gates to add to said first localization netlist.

### Claim 3 (depends on 2)

The system of claim 2, further comprising means for forming said first localization netlist and said set of gates to add from a set of one or more registers and one or more non-registers.

### Claim 4 (depends on 1)

The system of claim 1, wherein said means for computing said min-cut further comprises means for, upon determining a register to be within said first set of gates to be added, computing said min-cut on both a next state and an initial value cone of said register.

### Claim 5 (depends on 1)

The system of claim 1, wherein said means for forming, means for computing, and means for obtaining iteratively operate in response to the detection of one or more spurious counterexamples on said final localized netlist.

### Claim 6

A machine-usable medium having a plurality of instructions processable by a machine embodied therein, wherein said plurality of instructions, when processed by said machine, causes said machine to perform a method comprising:
selecting a set of gates to add to a first localization netlist;
forming a refinement netlist;
computing a min-cut with sinks comprising one or more gates in said refinement netlist and sources comprising one or more inputs of an original netlist and one or more registers of said original netlist which are not part of said refinement netlist; and
obtaining a final localized netlist by adding one or more gates to said refinement netlist to grow said refinement netlist until reaching one or more cut-gates of said min-cut.

### Claim 7 (depends on 6)

The machine-usable medium of claim 6, wherein said step of forming said refinement netlist further comprises forming said refinement netlist by adding said first localization netlist and said set of gates to add to said first localization netlist.

### Claim 8 (depends on 6)

The machine-usable medium of claim 6, wherein said step of forming said first localization netlist and said set of gates to add from a set of one or more registers and one or more non-registers.

### Claim 9 (depends on 6)

The machine-usable medium of claim 6, wherein said step of computing said min-cut further comprises, upon determining a register to be within said first set of gates to be added, computing said min-cut on both a next state and an initial value cone of said register.

### Claim 10 (depends on 6)

The machine-usable medium of claim 6, further comprising iteratively applying said forming, computing, and obtaining steps in response to the detection of one or more spurious counterexamples on said final localized netlist.

### Claim 11 (depends on 6)

The machine-usable medium of claim 6, wherein the processable instructions are deployed to a server from a remote location.

### Claim 12 (depends on 6)

The machine-usable medium of claim 6, wherein the processable instructions are provided by a service provider to a customer on an on-demand basis.
