The most successful technologies for automatic verification of large industrial circuits are bounded model checking, abstraction, and iterative refinement. Previous work has demonstrated the ability to verify circuits with thousands of state elements achieving bounds of at most a couple of hundreds. In this paper we present several novel techniques for abstraction-based bounded model checking. Specifically, we introduce a constant-propagation technique to simplify the formulas submitted to the CNF SAT solver; we present a new proof-based iterative abstraction technique for bounded model checking; and we show how the two techniques can be combined. The experimental results demonstrate our ability to handle circuit with several thousands state elements reaching bounds nearing 1,000.

It is essential to formally ascertain whether the register-transfer level (RTL) validation effort effectively guarantees the correctness with respect to the design's architectural intent. The design's architectural intent can be expressed in formal properties. However, due to the capacity limitations of formal verification, these architectural properties cannot be directly verified on the RTL. As a result, a set of lower level RTL properties are developed and verified against the RTL modules. In a top-down design approach, the architect would ideally like to formally guarantee the coverage of the architectural intent at the time of creating the specifications for the component RTL modules (that is, before they are passed to the designers for implementation). In this paper, the authors present: 1) a method for checking whether the RTL properties are covering the architectural properties, that is, whether verifying the RTL properties guarantees the correctness of the design's architectural intent; 2) a method to identify which architectural properties are still uncovered, that is, not guaranteed by the RTL properties; and 3) a methodology for representing the gap between the specifications in a legible form

This work describes an algorithm of automata construction for LTL safety properties, suitable for bounded model checking. Existing automata construction methods are tailored to BDD-based symbolic model checking. The novelty of our approach is that we construct deterministic automata, unlike the standard approach, which constructs nondeterministic automata. We show that the proposed method has significant advantages for bounded model checking over traditional methods.

Existing methods for formal verification coverage compare a given specification with a given implementation, and evaluate the coverage gap in terms of quantitative metrics. We consider a new problem, namely to compare two formal temporal specifications and to find a set of additional temporal properties that close the coverage gap between the two specifications. In this paper we present: (1) the problem definition and motivation, (2) a methodology for computing the coverage gap between specifications, and (3) a methodology for representing the coverage gap as a collection of temporal properties that preserve the syntactic structure of the target specification.

We present a deterministic algorithm that computes st -connectivity in undirected graphs using O (log 4/3 n ) space. This improves the previous O (log 3/2 n ) bound of Nisan et al. [1992].

We present a deterministic algorithm that computes st-connectivity in undirected graphs using 0(log4f3 n) space.This improves the previous O(log3f2 n) bound of Nisan, Szemer6di and Wigderson [NSW92].

A common subproblem of DNF approximate counting and derandomizing RL is the discrepancy problem for combinatorial rectangles. We explicitly construct a poly(n)-size sample space that approximates the volume of any combinatorial rectangle in [n]/sup n/ to within o(1) error. The construction extends the previous techniques for the analogous hitting set problem, most notably via discrepancy preserving reductions.