Semilattices of Fault Semiautomata

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 = {M1, …,Mk} of ‘faulty’ semiautomata. To define multiple faults from S, we need a binary composition operation, say ⊙, on semiautomata, which is idempotent, commutative, and associative. Thus, one has the free semilattice S⊙ generated by S. In general, however, the single faults are not independent; a finite set E of equations of the form Mii ⊙…⊙Mih = Mj1 ⊙…⊙Mjk describes the relations among them. The pair (S, E) is a finite presentation of the quotient semilattice S ⊙ /η, where η 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.