Finding Multiple Equivalence-Preserving Transformations in Combinational Circuits through Incremental-SAT

This paper introduces an approach to effectively exploit incremental SAT in order to search for multiple equivalence-preserving transformations of combinational circuits. Typical applications, such as redundancy removal with observability and external care conditions, adequate abstractions and other optimizations used in a state-of-the-art SAT-based model checker, can reap benefits from the proposed strategies. Our techniques exploit SAT incrementality, by iteratively refining the set of candidate transformations with a counter-example driven analysis, until an unsatisfiable point is reached. The key point of our technique is the ability to address satisfiable instances first, where SAT solvers are generally much faster than with unsatisfiable runs. We also discuss partitioning and problem reduction issues, that are fundamental in order to provide a scalable approach. Experimental results show the effectiveness of the proposed strategies.     

Verification of Similar FSMs by Mixing Incremental Re-encoding, Reachability Analysis, and Combinational Checks

State space exploration is often used to prove properties about sequential behavior of Finite State Machines (FSMs). For example, equivalence of two machines is proved by analyzing the reachable state set of their product machine. Nevertheless, reachability analysis is infeasible on large practical examples. Combinational verification is far less expensive, but on the other hand its application is limited to combinational circuits, or particular design schemes. Finally, approximate techniques imply sufficient, not strictly necessary conditions.The purpose of this paper is to extend the applicability of purely combinational checks. This is generally achieved through state minimization, partitioning, and re-encoding the FSMs to factor out their differences. We focus on re-encoding. In particular, we present an incremental approach to re-encoding for verification that transforms the product machine traversal into a combinational verification in the best case, and into a computationally simpler product machine traversal in the general case.Experimental results demonstrate the effectiveness of this technique on medium-large circuits where other techniques may fail.     

Tyrosine phosphorylation and src family kinases control keratinocyte cell-cell adhesion

In their progression from the basal to upper differentiated layers of the epidermis, keratinocytes undergo significant structural changes, including establishment of close intercellular contacts. An important but so far unexplored question is how these early structural events are related to the biochemical pathways that trigger differentiation. We show here that beta-catenin, gamma-catenin/plakoglobin, and p120-Cas are all significantly tyrosine phosphorylated in primary mouse keratinocytes induced to differentiate by calcium, with a time course similar to that of cell junction formation. Together with these changes, there is an increased association of alpha-catenin and p120-Cas with E-cadherin, which is prevented by tyrosine kinase inhibition. Treatment of E-cadherin complexes with tyrosine-specific phosphatase reveals that the strength of alpha-catenin association is directly dependent on tyrosine phosphorylation. In parallel with the biochemical effects, tyrosine kinase inhibition suppresses formation of cell adhesive structures, and causes a significant reduction in adhesive strength of differentiating keratinocytes. The Fyn tyrosine kinase colocalizes with E-cadherin at the cell membrane in calcium-treated keratinocytes. Consistent with an involvement of this kinase, fyn-deficient keratinocytes have strongly decreased tyrosine phosphorylation levels of beta- and gamma-catenins and p120-Cas, and structural and functional abnormalities in cell adhesion similar to those caused by tyrosine kinase inhibitors. Whereas skin of fyn-/- mice appears normal, skin of mice with a disruption in both the fyn and src genes shows intrinsically reduced tyrosine phosphorylation of beta-catenin, strongly decreased p120-Cas levels, and important structural changes consistent with impaired keratinocyte cell adhesion. Thus, unlike what has been proposed for oncogene-transformed or mitogenically stimulated cells, in differentiating keratinocytes tyrosine phosphorylation plays a positive role in control of cell adhesion, and this regulatory function appears to be important both in vitro and in vivo.     

Are BDDs still alive within sequential verification?

This work proposes a fully BDD-based approach based on: mixing forward and backward traversals, dovetailing approximate and exact methods, adopting guided and partitioned searches, and using conjunctive decompositions and generalized-cofactor-based BDD simplifications. The method is exact, i.e., it does not produce false negatives or positives, and reaps relevant performance enhancements from an appropriate tradeoff among the component methodologies.The resulting verification strategy is able, on one hand, to improve standard BDD-based algorithms, and, on the other hand, to compete with SAT-based tools on a broader range of circuit sizes.We experimentally compare our approach with three state-of-the-art freely available techniques. The first and second ones are SAT-based strategies, i.e., bounded model checking implemented within the NuSMV and the VIS tools (using Chaff as SAT engine). The third one is a BDD-based methodology, i.e., approximate reachability dont cares model checking implemented within the VIS tool. Results show interesting improvements in terms of both efficiency and power. They demonstrate how BDDs are able to accomplish larger verification tasks and to efficiently deal with high sequential depths.     

An approach to sequential circuit diagnosis based on formal verification techniques

This article deals with the generation of exact diagnostic trees for real-size synchronous sequential circuits. Starting from existing detection-oriented test patterns, a modified fault simulator is used for assessing their diagnostic power, which, in general, is not satisfactory. A diagnostic procedure for improving it is described that successfully exploits symbolic FSM equivalence proof algorithms. In order to resort to costly techniques, such as product machine traversal, only when really needed, special checks are performed to verify combinational identity and identity on reachable states. As all faults are attributed to theirequivalence class, a complete and exact diagnostic tree can be built. Experimental results on ISCAS'89 circuits show the feasibility of the approach and support the claim that, for the first time, diagnosing real-world synchronous sequential circuits has become feasible.     

A graph‐labeling approach for efficient cone‐of‐influence computation in model‐checking problems with multiple properties

In order to make model checking applicable to realistic problems, simplification techniques are essential. Models may be simplified eliminating the variables that do not appear in the cone‐of‐influence (COI) of the properties under verification. Efficient COI computation is thus required. Algorithms based on depth‐first visits may become cumbersome when they must be applied several times; for instance, when multiple properties must be verified on the same model. An alternative is to resort to graph‐labeling methods, trading‐off time for memory. Modeling the problem in terms of graphs, this paper develops a technique based on bitmaps that keeps the amount of memory needed within acceptable limits. The paper also describes a portfolio of optimizations of the original algorithm that allow even more reductions in memory usage. Experimental results show that the basic algorithm and its optimized versions perform very well on standard benchmark circuits used in the model‐checking community. Copyright © 2015 John Wiley & Sons, Ltd.     

Entropic recoil separation of long DNA molecules

A novel technique that can rapidly separate long-strand polymers according to length is presented. The separation mechanism is mediated by a confinement-induced entropic force at the abrupt interface between regions of vastly different configuration entropy. To demonstrate this technique, DNA molecules were partially inserted into a dense array of nanopillars (an entropically unfavorable region) using a pulsed electric field and allowed to relax to their natural state by removal of the field. Molecules of dissimilar lengths (T2 and T7 coliphage DNA) were inserted into this region in such a way that shorter molecules were fully inserted in this region, while longer molecules remained partially across the interface. The longer T2 molecules were observed to recoil entirely out of the pillar array, leaving the shorter T7 molecules inserted, and effecting separation of the two species in a single step. To show how this method can be used for separation of unknown samples, the inserting electric field was pulsed for progressively longer times, allowing passage of progressively longer molecules and producing the equivalent of a conventional electropherogram. The effects limiting resolution in this device are discussed, and the expected separating power of a multistage device is reported. The extracted resolution and running separation time compare favorably with current conventional separation techniques.