Abstract In the field of formal verification, certifying proofs serve as compelling evidence to demonstrate the correctness of a model within a deductive system. These proofs can be automatically generated as a by-product of the verification process and are key artifacts for high-assurance systems. Their significance lies in their ability to be independently verified by proof checkers, which provides a more convenient approach than certifying the tools that generate them. Modern model checking algorithms adopt deductive methods and usually generate proofs in terms of inductive invariants, assuming that these apply to the original system under verification. Model checkers, though, often make use of a range of complex pre-processing simplifications and transformations to ease the verification process, which add another layer of complexity to the generation of proofs. In this paper, we present a novel approach for certifying model checking results exploiting a theorem prover and a theory of temporal deductive rules that can support various kinds of transformations and simplification of the original circuit. We implemented and experimentally evaluated our contribution on invariants generated using two state-of-the-art model checkers, nuXmv and PdTRAV, and by defining a set of rules within a theorem prover, to validate each certificate.

Machine learning (ML) is ever more frequently used as a tool to aid decision-making. The need to understand the decisions made by ML algorithms has sparked a renewed interest in explainable ML models. A number of known models are often regarded as interpretable by human decision-makers with varying degrees of difficulty. The size of such models plays a crucial role in determining how easily they can be understood by a human. In this paper1 we propose the use of Binary Decision Diagrams (BDDs) as an interpretable ML model. BDDs can be deemed as interpretable as decision trees (DTs) while offering a often more compact representation due to node sharing. Fixed variable ordering also allows for more concise explanations. We propose a SAT-based approach for learning optimal BDDs that exhibit perfect accuracy on training data. We also explore heuristic methods for computing sub-optimal BDDs, in order to improve scalability.

Motivated by the need to understand the behaviour of complex machine learning (ML) models, there has been recent interest in learning optimal (or sub-optimal) decision trees (DTs). This interest is explained by the fact that DTs are widely regarded as interpretable by human decision makers. An alternative to DTs are Binary Decision Diagrams (BDDs), which can be deemed interpretable. Compared to DTs, and despite a fixed variable order, BDDs offer the advantage of more compact representations in practice, due to node sharing. Moreover, there is also extensive experience in the efficient manipulation of BDDs. Our work proposes preliminary inroads in two main directions: (a) proposing a SAT-based model for computing a decision tree as the smallest Reduced Ordered Binary Decision Diagram, consistent with given training data; and (b) exploring heuristic approaches for deriving sub-optimal (i.e., not minimal) ROBDDs, in order to improve the scalability of the proposed technique. The heuristic approach is related to recent work on using BDDs for classification. Whereas previous works addressed size reduction by general logic synthesis techniques, our work adds the contribution of generalized cofactors, that are a well-known compaction technique specific to BDDs, once a care (or equivalently a don't care) set is given. Preliminary experimental results are also provided, proposing a direct comparison between optimal and sub-optimal solutions, as well as an evaluation of the impact of the proposed size reduction steps.

We address the problem of reducing the size of Craig's interpolants (ITPs) used in SAT-based model checking. Whereas it is well known that ITPs are highly redundant, their compaction is typically tackled by reducing the proof graph and/or by exploiting standard logic synthesis techniques. Furthermore, strengthening and weakening have been studied as options to control ITP quality. In this paper,1 we propose an SAT-based ITP weakening/strengthening technique, for ITP compaction, where the UNSAT core extracted from an additional SAT query is used to obtain a gate-level abstraction of the ITP. The abstraction introduces fresh new variables at gate cuts that must be quantified out in order to obtain a valid ITP. We show how to efficiently quantify them out, by working on a negation normal form representation of the circuit. This paper includes an experimental evaluation, showing the benefits of the proposed approach, on a set of benchmark ITPs arising from hardware model checking problems.

Electric vehicles are accelerating the world's transition to sustainable energy.Nevertheless, the lack of a proper charging station infrastructure in many real implementations still represents an obstacle for the spread of such a technology.In this paper, we present a real case application of optimization techniques in order to solve the location problem of electric charging stations in the district of Biella, Italy.The plan is composed by several progressive installations and decision makers pursue several objectives that might be in contrast.For this reason, we present an innovative framework based on the comparison of several ad-hoc Key Performance Indicators for evaluating many different aspects of a location solution.

We address the problem of reducing the size of Craig's interpolants used in SAT-based model checking. Craig's interpolants are AND-OR circuits, generated by post-processing refutation proofs of SAT solvers. Being highly redundant, their compaction is typically tackled by reducing the proof graph and/or by exploiting standard logic synthesis techniques. In this paper, we propose a set of ad-hoc logic synthesis functions that, revisiting known logic synthesis approaches, specifically address speed and scalability. Though general and not restricted to interpolants, these techniques target the main sources of redundancy in combinational circuits. This paper includes an experimental evaluation, showing the benefits of the proposed techniques, on a set of benchmark interpolants arising from hardware model checking problems.

This paper presents a simple 7/2-approximation algorithm for the Maximum Duo-Preservation String Mapping (MPSM) problem. This problem is complementary to the classical and well studied min common string partition problem (MCSP), that computes the minimal edit distance between two strings when the only operation allowed is to shift blocks of characters. The algorithm improves on the previously best-known 4-approximation algorithm by computing a simple local optimum.

We address the problem of reducing the size of Craig interpolants used in SAT-based Model Checking. Craig interpolants are AND-OR circuits, generated by post-processing refutation proofs of SAT solvers. Whereas it is well known that interpolants are highly redundant, their compaction is typically tackled by reducing the proof graph and/or by exploiting standard logic synthesis techniques. Furthermore, strengthening and weakening have been studied as an option to control interpolant quality. In this paper we propose two interpolant compaction techniques: (1) A set of ad-hoc logic synthesis functions that, revisiting known logic synthesis approaches, specifically address speed and scalability. Though general and not restricted to interpolants, these techniques target the main sources of redundancy in interpolant circuits. (2) An interpolant weakening technique, where the UNSAT core extracted from an additional SAT query is used to obtain a gate-level abstraction of the interpolant. The abstraction introduces fresh new variables at gate cuts that must be quantified out in order to obtain a valid interpolant. We show how to efficiently quantify them out, by working on an NNF representation of the circuit. The paper includes an experimental evaluation, showing the benefits of the proposed techniques, on a set of benchmark interpolants arising from both hardware and software model checking problems.

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.

Constraints represent a key component of state-of-the-art verification tools based on compositional approaches and assume-guarantee reasoning. In recent years, most of the research efforts on verification constraints have focused on defining formats and techniques to encode, or to synthesize, constraints starting from the specification of the design. In this paper, we analyze the impact of constraints on the performance of model checking tools, and we discuss how to effectively exploit them. We also introduce an approach to explicitly derive verification constraints hidden in the design and/or in the property under verification. Such constraints may simply come from true design constraints, embedded within the properties, or may be generated in the general effort to reduce or partition the state space. Experimental results show that, in both cases, we can reap benefits for the overall verification process in several hard-to-solve designs, where we obtain speed-ups of more than one order of magnitude.

Interpolant-based model checking has been shown effective on large verification instances, as it efficiently combines automated abstraction and fixed-point checks. On the other hand, methods based on variable quantification have proved their ability to remove free inputs, thus projecting the search space over state variables. In this paper we propose an integrated approach combining the abstraction power of interpolation with techniques relying on AIG and/or BDD representations of states, supporting variable quantification and fixed-point checks. The underlying idea of this combination is to adopt AIG- or BDD-based quantifications to limit and restrict the search space (and the complexity) of the interpolant-based approach. The exploited strategies, individually well-known, are integrated with a new flavor, specifically designed to improve their effectiveness on large verification instances. Experimental results, oriented to hard-to-solve verification problems, show the robustness of our approach.

This paper addresses the field of unbounded model checking (UMC) based on SAT engines, where Craig interpolants have recently gained wide acceptance as an automated abstraction technique. We start from the observation that interpolants can be quite effective on large verification instances. As they operate on SAT-generated refutation proofs, interpolants are very good at automatically abstract facts that are not significant for proofs. In this work, we push forward the new idea of generating abstractions without resorting to SAT proofs, and to accept (reject) abstractions whenever they (do not) fulfill given adequacy constraints. We propose an integrated approach smoothly combining the capabilities of interpolation with abstraction and over-approximation techniques, that do not directly derive from SAT refutation proofs. The driving idea of this combination is to incrementally generate, by refinement, an abstract (over-approximate) image, built up from equivalences, implications, ternary and localization abstraction, then (eventually) from SAT refutation proofs. Experimental results, derived from the verification of hard problems, show the robustness of our approach.

The usefulness of Bounded Model Checking (BMC) based on propositional satisfiability (SAT) methods has recently proven its efficacy for bug hunting. BDD based tools are able to verify broader sets of properties (e.g. CTL formulas) but recent experimental comparisons between SAT and BDDs in formal verification lead to the conclusion that SAT approaches are more robust and scalable than BDD techniques.In this work we extend BDD-based verification to larger circuit and problem sizes, so that it can indeed compete with SAT based tools. The approach we propose solves Bounded Model Checking problems using BDDs. In order to cope with larger models it exploits approximate traversals, yet it is exact, i.e. it does not produce false negatives or positives. It reaps relevant performance enhancements from mixed forward and backward, approximate and exact traversals, guided search, conjunctive decompositions and generalized cofactor based BDD simplifications.We experimentally compare our tool with BMC in NuSMV using mchaff as SAT engine, and we show that BDDs are able to accomplish large verification tasks, and they can better cope with increasing sequential depths.

The core computation in BDD-based symbolic synthesis and verification is forming the image and pre-image of sets of states under the transition relation characterizing the sequential behavior of the design. Computing an image or a pre-image consists of ordering the latch transition relations, clustering them and eventually re-ordering the clusters. Existing algorithms are mainly limited by memory resources. To make them as efficient as possible, we address a set of heuristics with the main target of minimizing the memory used during image computation. They include a dynamic heuristic to order the latch relations, a dynamic framework to cluster them, and the application of conjunctive partitioning during image computation. We provide and integrate a set of algorithms and we report references and comparisons with recent work. Experimental results are given to demonstrate the efficiency and robustness of the approach.

We address BDD based reachability analysis, which is the core technique of symbolic sequential verification and Model Checking. Within this framework, non purely breadth-first and guided traversals have shown their value to improve efficiency by reducing memory consumption for BDD representation. We propose a guided search strategy exploiting performance statistics. These activity figures are gathered through a continuous and dynamic learning process on a variable-by-variable basis. This technique is currently integrated with the reachability analysis routine, as it is fully compatible with dynamic reordering and allows multiple partial traversal phases. We thus move away from the static and manual schemes, which are one of the main limitations of previous approaches. Experiments are given to demonstrate the efficiency and robustness of the approach.

Symbolic techniques have undergone major improvements in the last few gears. Nevertheless, applications are still limited by memory size and time constraints. As a consequence, extending their applicability to larger and real circuits is still a key issue. Within this framework, we introduce "activity profiles" as a novel technique to characterize finite state machines described by their transition relation. In our methodology, a "learning phase" is used to collect activity measures. They are gathered, in an inexpensive way, for each binary decision diagram node of the transition relation. They indicate the activity the node has been involved in, as an estimate of its correlation with space and/or time costs. The above information can be used for several purposes. In particular, we present an application of activity profiles in the field of reachability analysis, to enhance memory and time performance of traversals. More specifically, we use transition relation subsetting in order to traverse the state transition graph in a nonpurely breadth-first, guided and multistep fashion. Comparisons with other state-of-the-art approaches show that our sequence of partial traversals produces "best-ever" results for all the large benchmarks analyzed.

Symbolic techniques have undergone major improvements in the last few years.Nevertheless they are still limited by the size of the involved BDDs, and extending their applicability to larger and real circuits is a key issue.Within this framework, we introduce "activity profiles" as a novel technique to characterize transition relations.In our methodology a learning phase is used to collect activity measures, related to time and space cost, for each BDD node of the transition relation.We use inexpensive reachability analysis as learning technique, and we operate within inner steps of image computations involving the transition relation and state sets.The above informations can be used for several purposes.In particular, we present an application of activity profiles in the field of reachability analysis itself.We propose transition relation subsetting and partial traversals of the state transition graph.We show that a sequence of partial traversals is able to complete a reachability analysis problem with smaller memory requirement and improved time performance.

In this paper we address the problem of computing silent paths in an Finite State Machine (FSM). These paths are characterized by no observable activity under constant inputs, and can be used for a variety of applications, from verification, to synthesis, to simulation. First, we describe a new approach to compute the Timed Transition Relation of an FSM. Then, we concentrate on applying the methodology to simulation of reactive behaviours. In this field, we automatically extract a BDD-based behavioral model from the RT or gate level description. The behavioral model as able to "jump" in time and to avoid the simulation of internal events. Finally, we discuss a set of promising experimental results in a simulation environment under the Ptolemy simulator.

Binary decision diagrams (BDD's) are a state-of-the-art core technique for the symbolic representation and manipulation of Boolean functions, relations and finite sets. Many computer-aided design (CAD) applications resort to them, but size and time efficiency restrict their applicability to medium-small designs. We concentrate on complex operators used in symbolic manipulation. We analyze and optimize their performance by means of new dynamic partitioning strategies. We propose a novel quick algorithm for the estimation of cofactor size, and a technique to choose splitting variables according to their discrimination power, so that their cofactors may be optimized by different variable orderings (tending to the more flexible FBDDs). Furthermore, we analyze time efficiency and the impact of hashing/caching on BDD-based operators. We finally include an experimental observation of memory usage and running time for operators applied in symbolic manipulation.

Binary Decision Diagrams (BDDs) are the state-of-the-art technique for many synthesis, verification and testing problems in CAD for VLSI. Many researchers proposed optimized BDD—based representations, but in many complex applications the (working) memory required is still too much. Virtual memory is no alternative solution, because if the working set size for a program is large and memory accesses are random, an extremely large number of page faults significantly modifies the performance of the software. This paper proposes a solution to this problem for a specific application, namely BDD—based exploration of large state spaces, an issue often found in CAD for VLSI. Our ‘divide—and—conquer’ approach for reachability analysis is based on decomposition of state sets carried out at different levels and on an effective use of mass memory. As a result, we are able to explore the state space of large Finite State Machines. At the same time, the technique we develop is orthogonal to a variety of symbolic techniques and graph manipulation procedures and it allows reducing complexity of very common operations. Experimental results, on well known synchronous benchmarks usually used in the field of CAD for VLSI, show that this approach is particularly effective on larger problems as decomposition decreases the amount of working memory, avoids page faulting and makes the overall process more efficient. © 1998 John Wiley & Sons, Ltd.

BDDs are the state-of-the-art technique for representing and manipulating Boolean functions. Their introduction caused a major leap forward in synthesis, verification, and testing. However, they are often unmanageable because of the large amount of nodes. To attack this problem, we insert auxiliary variables that decompose monolithic BDDs in smaller ones. This method works very well for Boolean function representation. As far as combinational circuits are concerned, representing their functions is the main issue. Going into the sequential domain, we focus on traversal techniques. We show that, once we have Boolean functions in decomposed form, symbolic manipulations are viable and efficient. We investigate the relation between auxiliary variables and static and dynamic ordering strategies. Experimental evidence shows that we achieve a certain degree of independence from variable ordering. Thus, this approach can be an alternative to dynamic re-ordering. Experimental results on Boolean function representation, and exact and approximate forward symbolic traversal of FSMs, demonstrate the benefits both in terms of memory requirements and of CPU time.

Extending the applicability of reachability analysis to large andreal circuits is a key issue.In fact they are still limited forthe following reasons: peak BDD size during image computation,BDD explosion for representing state sets and very highsequential depth.Following the promising trend of partitioning and problem decomposition,we present a new approach based on a disjunctivepartitioned transition relation and on an improved iterativesquaring.In this approach a Finite State Machine is decomposedand traversed one "functioning-mode" at a time bymeans of the "disjunctive" partitioned approach.The overall algorithm aims at lowering the intermediate peakBDD size pushing further reachability analysis.Experimentson a few industrial circuits containing counters and on somelarge benchmarks show the feasibility of the approach.

We define the new exist generalized cofactor and image restrictor, a Boolean operator that supports the distributivity of conjunction and existential quantification. It finds a major application in existentially quantified products, like the transition relations that describe the sequential behavior of synchronous sequential circuits. We prove that the exist cofactor extends and includes the previous uses of the cofactor as an image restrictor. Aware of the fact that cofactoring sometimes makes binary decision diagrams (BDD's) more complex, we introduce selective cofactoring, i.e., we cofactor only subsets of functions, allowing a mix between cofactoring and conjunction. As a result, we propose an image computation method that includes techniques presented earlier. Experimental results show that we are able to reduce memory peaks, to lower overall memory occupation, and to reduce CPU time for symbolic traversal of some large benchmark circuits. We are also able to present experimental evidence on circuits that, to the best of our knowledge, have not yet been traversed.

BDD-based symbolic traversals are the state-of-the-art technique for reachability analysis of finite state machines. They are currently limited to medium-small circuits for two reasons: peak BDD size during image computation and BDD explosion for representing state sets. Starting from these limits, this paper presents can optimized traversal technique particularly oriented to the exact exploration of the state space of large machines. This is possible thanks to: temporary simplification of a finite state machine by removing some of its state elements; and a "divide-and-conquer" approach based on state set decomposition. An effective use of secondary memory allows us to store relevant portions of BDDs and to regularize access to memory, resulting in less page faults. Experimental results show that this approach is particularly effective on the larger ISCAS'89 and ISCAS'89-addendum'93 circuits.

Synthesis and optimization of large finite-state machines has improved dramatically over the last few years with the introduction and rapid improvement of symbolic-state manipulation techniques. The algorithms efficiently visit each reachable state in the machine while computing and storing information about these states. We propose a new technique for improving the efficacy of traversal algorithms: re-encoding the states of the machine to more efficiently represent state sets or state transitions, or to more efficiently compute the next set of states. Our technique can be embedded in existing traversal algorithms. Experiments reveal that re-encoding can indeed reduce the time and/or space required for traversal.

Article Free Access Share on Auxiliary variables for extending symbolic traversal techniques to data paths Authors: Gianpiero Cabodi Politecnico di Torino, Dipartimento di Automatica e Informatica, Turin, Italy Politecnico di Torino, Dipartimento di Automatica e Informatica, Turin, ItalyView Profile , Paolo Camurati Politecnico di Torino, Dipartimento di Automatica e Informatica, Turin, Italy Politecnico di Torino, Dipartimento di Automatica e Informatica, Turin, ItalyView Profile , Stefano Quer Politecnico di Torino, Dipartimento di Automatica e Informatica, Turin, Italy Politecnico di Torino, Dipartimento di Automatica e Informatica, Turin, ItalyView Profile Authors Info & Claims DAC '94: Proceedings of the 31st annual Design Automation ConferenceJune 1994 Pages 289–293https://doi.org/10.1145/196244.196380Published:06 June 1994Publication History 5citation122DownloadsMetricsTotal Citations5Total Downloads122Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Symbolic state space traversal techniques are best on control-dominated circuits, not on data paths. This paper extends their applicability to regular structures commonly found in data paths by using auxiliary variables to decompose and to manipulate Boolean functions in decomposed form. Experimental results demonstrate the gain both in terms of binary decision diagram (BDD) size and CPU time.>

Most symbolic state space exploration techniques for finite state machines (FSMs) are exact and based on forward traversal, but limited to medium-size circuits. Approximate forward traversal deals with bigger circuits at the expense of exactness. Backward traversal focuses the search process on the property under scrutiny, but it also takes into account many unreachable states. For this reason, it works mainly on small circuits. This paper presents novel techniques that make exact symbolic backward traversal feasible also for large circuits. The key point is an efficient pruning of the search space, exploiting information coming from an approximate forward reachability analysis. Experimental evidence shows that, for the first time, the larger ISCAS'89 and MCNC circuits are symbolically manipulated in an exact way and the test patterns for them are generated.>

Symbolic state space exploration techniques proved to be useful not only in formal verification and synthesis, but also in testing. Most of them are based on exact forward or backward traversal. As an alternative, approximate forward traversal algorithms have been proposed, but they are not immediately applicable to test pattern generation. This paper presents strategies for approximate forward traversal, then it combines approximate forward traversal and backward traversal for generating test patterns for hard to detect faults. Efficient search space pruning is obtained by means of cofactoring. Experimental results show that the speed up ranges from 2 to more than 50.>

Until now, symbolic FSM state space exploration techniques were limited to small circuits. This paper presents a combination of approximate forward and exact backward traversal that handles larger circuits. For the first time, we have been able to generate test patterns for or to tag as undetectable the faults of some ISCAS'89 and MCNC benchmarks never considered before.

Process algebras are a suitable formalism both for system-level description and for ATPG with formal verification techniques. A functional fault model for system-level descriptions is presented and experimental data are reported. The contributions of this paper are the definition of a general-purpose fault model for concurrently evolving processes and the implementation of a test pattern generation procedure, as a variant of the testing equivalence proof. A complete test system is implemented, allowing one to describe systems, describe faults and generate test patterns within the same environment.>

High-quality embedded memory testing is increasingly important and a BIST scheme seems advantageous. Industrial experience at Italtel, a telecom company, confirms it. The scheme implements in hardware the test pattern generation algorithm proposed by R. Nair, S.M. Thatte, and J.A. Abraham /spl lsqb/1978/spl rsqb/, extending it to word-based memories. Several goodness criteria are satisfied, as the experimental results confirm.>

Symbolic state space traversal techniques are one of the most notable achievements in the fields of formal verification and of automated synthesis. Transition functions and transition relations are two alternative approaches. In terms of efficiency, transition functions have proven to be superior, although the transition relation is much more expressive. The paper brings the transition relation back to a new life, profiting from recent advancements in the fields of Boolean function representation, simplification, and image computation represented by BDDs and by the generalized cofactor operator. A theoretical result allows us to considerably simplify both the process of building the transition relation and of traversing the state space. Experimental results show that performances similar to those of the transition function are obtained.>

This paper‘ deals with the generation of diagnostic test sequences for real-size synchronous sequential circuits. A modified fault simulator is used for assessing the diagnostic power of existing detection-oriented test patterns and a diagnostic procedure for generating new ones is described. The diagnostic procedure successfully exploits symbolic FSM equivalence proof algorithms. In order to resort to product machine traversal only when really needed, special checks are perfo:rrned to verify combinational identity and identity on rt:achable states. As all faults are attributed to their equivalence class, this method may be used to build a complete and exact diagnostic tree. Experimental results on ISCAS’89 circuits show the feasibility of the’ approach ’.

Particular design environments, e.g., those based on partial scan, may prevent design for testability techniques from reducing testing to a combinational problem: ATPG for sequential devices thus remains a challenge. Random and deterministic structure-oriented techniques are state-of-the-art, but there is a growing interest in methods that resort to the automaton of the circuit. The authors present SETA, a sequential test generator based on automata, an ATPG applicable to synchronous circuits working in the fundamental mode. SETA generates test patterns while trying to disprove the equivalence of two automata. SETA is simulation-based: within the theoretical framework of the product machine, state-of-the-art simulation techniques are used to yield satisfactory experimental results on the ISCAS89 benchmark set.>

The authors present a method to prove equivalence of a pair of FSMs, described at the gate level with D-type flip-flops and a reset signal available to bring them into the all-zero initial state. This method restricts investigation to that minimum subset of states that can be reached from the reset condition and are necessary to reach the goal. The equivalence condition is expressed in theoretical terms within the framework of the product machine. Without any loss of information, it is possible to reduce the product machine to a deterministic finite automaton (DFA). considerably reducing the number of states. The DFA is dynamically built by an explicit enumeration algorithm and, in general, only a very small part of the automaton is actually considered. The equivalence condition becomes a proof of the reachability of the DFA's final state. Search is performed in breadth-first. Experimental results on some pairs of ISCAS'89 circuits are reported.>

Abstract This paper presents TPDL (extended temporal profile description language), a general‐purpose language to observe and condition dynamic systems by means of temporal and logical expressions. It describes how time is modelled in TPDL, gives an overview of the language through its basic types, primitives and conditional constructs, and its use in computer‐aided design of digital systems. The paper discusses TPDL's facilities to support the description of hardware behaviour, to define the environment in which devices operate, and to observe and control both circuits and environments. The characteristics of the language are demonstrated through some representative examples.

The authors present a novel ATPG (automatic test pattern generation) algorithm, based on PODEM, that makes diagnostic test pattern generation feasible for medium-sized combinational circuits described at the gate level with the single-stuck-at-fault assumption. The input to the ATPG is a couple of faults, and either the output is a test pattern that distinguishes them or they are tagged as indistinguishable. The need to consider the fault-free circuit and the two faulty circuits at the same time required the extension of the algebra to encompass two additional values, Delta and delta . A Delta appears on the nodes of the circuit whenever a difference between the two faulty circuits exists. The presence of a delta marks the locations where a difference might exist if the X values on one or both faulty circuits were suitably set. The algorithm excites and propagates Delta s onto the primary outputs and is thus called the Delta -algorithm. Preliminary results on a set of benchmark circuits are reported.>

The authors present the application of formal verification techniques to the MTI (Microprocesseur a test integre) microprocessor. The device is described and verified using a functional model. The authors note that the application is a real, rather than a verification-oriented microprocessor, whose description was available to them under the form of schematic and timing diagrams and as output of CAD (computer-aided design) tools. The effort is two-fold: (1) the authors verify the MTI microprocessor, finding some subtle bugs which had escaped the designers' attention, and (2) they develop a methodology whose applicability ranges beyond the particular case it has been demonstrated on.>

The authors present a comparative approach to some testability analysis methods for application to VLSI devices. Using a common framework of implementations and test cases, they compared the results between analysis methods and with those provided by fault simulation or exact calculation where possible. The methods dealt with are the weighted averaging algorithm, COP, the cutting algorithm, Stafan, and Predict.>

A description is given of ESTA, an expert system for the automation of design for testability (DFT) verification. The system takes descriptions written in a conventional hardware description language as input, translates them into a intermediate Prolog form and checks whether they comply either with the level sensitive scan design (LSSD) DFT method of B. Eichelberger and T.W. Williams (1977) or the built-in logic block observation (BILBO) DFT techniques of B. Konemann et al. (1979).>