1999 | OriginalPaper | Buchkapitel
Semilattices of Fault Semiautomata
verfasst von : Janusz A. Brzozowski, Helmut Jürgensen
Erschienen in: Jewels are Forever
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.