We introduce a typed λ-calculus which allows the use of exceptions in the ML style. It is an extension of the system $AF_2$ of Krivine & Leivant (Krivine, 1990; Leivant, 1983). We show its main properties: confluence, strong normalization and weak subject reduction. The system satisfies the “the proof as program” paradigm as in $AF_2$ . Moreover, the underlined logic of our system is intuitionistic logic.

Abstract We give a direct, purely arithmetical and elementary proof of the strong normalization of the cut-elimination procedure for full (i.e., in presence of all the usual connectives) classical natural deduction.

High defect coverage requires good coverage of different fault types. In this paper, we present a comprehensive test vector generation technique for BIST, called Random Single Input Change (RSIC) generation, that can be used to generate tests for many arbitrary misbehaviors that can occur in digital systems, thus providing a single on-chip test generation solution.

Abstract The λμ-calculus is an extension of the λ-calculus that has been introduced by M Parigot to give an algorithmic content to classical proofs. We show that Böhm's theorem fails in this calculus.

Synchronous systems can be distributed using different schemes of distribution. One possible distribution scheme is transforming the synchronous systems into a globally asynchronous locally synchronous system in which each site behaves synchronously while the exchanges between sites are asynchronous; this is a case of synchronous distributed systems. However, the obtained synchronous distributed system will present some bad behaviors due to delays introduced by the partial asynchronous behavior. Thus, we introduce order-insensitivity by analogy with delay-insensitivity of asynchronous hardware in order to have the same behavior in distributed and centralized implementations. This property characterizes systems where the parallel execution is equivalent to all possible sequential executions. Moreover, this property is not an intrinsic property to the state machine but only of its implementation. Consequently, we propose an algorithm for transforming an order-sensitive transition function into an equivalent order-insensitive one.

For a combinational fault, the probability of nondetection decreases exponentially with the test length L: /spl epsiv/=(1-p/sub f/)/sup L/, where p/sub f/ is the probability of detecting the fault f by a random test vector. For a sequential fault, the problem is more complex because of the memory effect (the probability of detection at time l depends on the vectors previously applied) and the exact solution requires the analysis of a Markov chain modeling the detection process. This paper shows that there is a value, obtained from the transition matrix of the Markov chain, which can take the place of p/sub f/ when the test length is relatively long (this value is different from the average detection probability). From this result and taking into account a particular property of bounded faults in RAMs, several results concerning these faults, already observed by several authors, are shown.

This paper presents an algebraic method allowing an accurate analysis of delay faults. This method is based on the fact that some input values remain constant when two successive input vectors are applied. For a transition between two input states, the output function is reduced to a function of few variables. An analysis of the reduced function allows one to obtain the delay faults which are detected by the corresponding transition. The analysis allows one to know if a fault is robustly testable or non robustly testable and validatable, or weakly verifiable: in every case the corresponding tests are obtained. An application of the results to random testing of faults allows one to observe that some non robustly testable faults are easier to detect than some robustly testable faults.

Abstract Storage operators have been introduced by J. L. Krivine in [5] they are closed λ-terms which, for a data type, allow one to simulate a “call by value” while using the “call by name” strategy. In this paper, we introduce the directed λ-calculus and show that it has the usual properties of the ordinary λ-calculus. With this calculus we get an equivalent—and simple—definition of the storage operators that allows to show some of their properties: • the stability of the set of storage operators under the β-equivalence (Theorem 5.1.1); • the undecidability (and semidecidability) of the problem “is a closed λ-term t a storage operator for a finite set of closed normal λ-terms?” (Theorems 5.2.2 and 5.2.3); • the existence of storage operators for every finite set of closed normal λ-terms (Theorem 5.4.3); • the computation time of the “storage operation” (Theorem 5.5.2).

For random test length evaluation, the usual approach considers only the fault that is most difficult to detect; this is pessimistic. The fault distribution in the batch of tested circuits should be taken into account. Since this information is not known before the test experiment, hypotheses on fault occurrence probabilities have to be made. This paper shows, through several simulations, that the test length does not depend very much on the fault occurrence hypotheses.>

Two continuous Petri net (CPN) models involving time are defined. They differ by the calculation of the instantaneous firing speeds of the transitions. Both can be used to approximate a timed Petri net. The first model considers constant firing speeds (constant-speed CPN, CCPN). It is very easy to simulate. The second model considers firing speeds depending on the marking (variable speed CPN, VCPN). It provides a better approximation, but its simulation is longer because the markings and speeds are given by differential equations. The authors introduce a third model, which has the advantages of the two preceding ones. This model represents the asymptotic behavior of the VCPN. Their precision is similar. It is as easy to simulate as the CCPN.>

The probability of a fault-free signature has been calculated in the above-named paper (see ibid., vol.C-35, no.9, p.830-7 (1986)) and in an earlier paper by the same author (see ibid., vol.C-29, no.7, p.668-73 (1980)). Implicitly, it was considered as the probability of masking due to signature analysis. It is shown here that this does not correspond exactly to the probability of aliasing. A new definition is given. The difference centers on the event where there are no bit errors in the data to be compressed. When the response of the circuit is correct, the signature is fault-free. However, there is no aliasing.>

It is shown how random testing experiments can be used for fault diagnosis. Starting from a prescribed set of faults, the result of the first experiment allows the authors (1) to determine a subset of faults which are compatible with this result and (2) to choose the second experiment, and so on. An algorithm (each step of which is an experiment) is given, and simulation results are presented.>

Test-pattern generation for high fault coverage is an expensive and time-consuming process. As an alternative circuits can be tested by applying random or pseudorandom patterns. To analyze random testing without fault simulation, the number of vectors that detect a fault in each fault class must be enumerated. A fault-detection function whose number of minterms is identical to the fault detectability is constructed. Extensions are made to the Cutting algorithm to evaluate the signal probability of the detection or its bounding functions. The signal probability can then be converted easily into an exact detectability or narrow detectability range associated with each fault.>

The number of (random) patterns required for random testing of RAMs (random-access memories), when classical fault models including pattern-sensitive faults are considered is determined. Markov chains are a powerful tool for this purpose. Single faults are considered first, and the influence of different parameters is analyzed. Double faults are then considered and arguments are presented to extend the results to all multiple-coupling faults. Those results are compared to the optimal or best-known number of test patterns required when deterministic testing is considered, for the same fault models.>

An aggregation method for performance evaluation of a line consisting of machines which may fail, and buffers, is presented. The first approach is based on a simple aggregation which associates an "equivalent machine" with a set consisting of two machines separated by a buffer. An improved approach takes the environment into account to define the "equivalent" machine.

A scheme of a good signature analysis by a linear feedback shift register (LFSR) is presented. It works for k-output circuits, even if k is greater than the register length. It is built according to rules which are presented in the correspondence, taking into account error models which are introduced. The rules are derived from a property which is formally shown for one kind of LFSR. However, some of them apply to other LFSR schemes too.

In [K] Keisler introduces a set theoretical relation WO(δ, x), where δ is an ordinal. This relation is characterized in ZF set theory by the following properties: (1) WO(0, x) if and only if there is a wellordering on x. (2) For δ > 0, WO(δ, x) if and only if there is a function ƒ with domain an ordinal λ such that: We denote WO∞ the collection denned by: WO∞(x) = ∃δ WO(δ, x). In [K] Keisler shows that countable transitive models of ZF + ∃x ¬ WO∞(x) have transitive uncountable elementary extensions with the same ordinals. Moreover for transitive models, satisfying ∃x ¬ WO∞(x) is also a necessary condition for the existence of an elementary extension with the same ordinals. (See [K bis] and also [K-M] where the connection with forcing is analysed.)

A compact testing method called feedback shift register testing (FSR testing) is presented and its properties, concerning detection and diagnosis, are given. The new notion of distinction potential is introduced. The proposed method is shown to have the maximum resolution and the maximum distinction potential that can be found for an m-bit signature.

This paper presents the new notion of minimal detecting transition sequence (MDTS). A detectable fault f in a circuit C is detected by any MDTS in a set Df called detection set associated with f. From a prescribed set of faults, we obtain a list of detection sets. This list of detection sets is calculated once for all, for a given circuit C. Once this list bas been obtained for a circuit, it may be used either to generate a deterministic test sequence, or to calculate random testing lengths within various hypothesis (input vector probabilities).

Totally self-checking 1-out-of-m checkers are known for all m except for m = 3. The principle of the 1-out-of-3 checker presented is the following: the 1-out-of-3 code is transcoded in a 1-out-of-4 code by a sequential circuit which is totally self-checking.

An universal cell (CUSA) permits one to realize any asynchronous automaton by associating such a cell with a state and a connection with a transition. There is no internal variable assignment and all kinds of hazards are avoided. In the first part of the paper we shall present the principle of the CUSA and the synthesis method using flow tables. It is an original method which enables one to reduce the number of cells and useful connections. In the second part, the method is adapted to a synthesis from a flow graph. In this graph, a node is associated with a state, not necessarily a total state, and a branch with a connection. This synthesis method is easy and systematic. CUSA are now being produced by industry and are available as IC's.

Fault detection by applying a random input sequence simultaneously to a network under test and to a reference network is conside-red. A distinction between testing quality and detection quality is given. The detection surface is introduced as a characteristic parameter of a combinational network. The results are applied to TTL combinational circuits.