Semilattices of Fault Semiautomata

J. A. Brzozowski and H. Jurgensen

Abstract

We study defects affecting state transitions in sequential circuits. The fault-free circuit is modeled by a semiautomaton M, and 'simple' defects, called single faults, by a set S = {M^1,...,M^k} of 'faulty' semiautomata. To define multiple faults from S, we need a binary composition operation, say \odot, on semiautomata, which is idempotent, commutative, and associative. Thus, one has the free semilattice S^\odot generated by S. In general, however, the single faults are not independent; a finite set E of equations of the form M^{i_1}\odot...\odot M^{i_h} = M^{j_1}\odot...\odot M^{j_k} describes the relations among them. The pair (S,E) is a finite presentation of the quotient semilattice S^\odot/\eta, where \eta is the smallest semilattice congruence containing E. In this paper, we first characterize such abstract quotient semilattices. We then survey the known results about random-access memories (RAMs) for the Thatte-Abraham fault model consisting of stuck-at, transition, and coupling faults. We present these results in a simplified semiautomaton model and give new characterizations of two fault semilattices.