id: 06028047
dt: j
an: 06028047
au: Brzozowski, Janusz; Ye, Yuli
ti: Gate circuits with feedback in finite multivalued algebras of transients.
so: J. Mult.-Val. Log. Soft Comput. 16, No. 1-2, 155-176 (2010).
py: 2010
pu: Old City Publishing, Philadelphia, PA
la: EN
cc: 
ut: algebra; circuit; dynamic; gate; hazard; multivalued; network; oscillation;
    simulation; static; ternary; transient
ci: 
li: http://www.oldcitypublishing.com/MVLSC/MVLSCcontents/MVLSCv16n1-2contents.html
ab: Summary: Multivalued simulation of gate circuits is an efficient method of
    detecting hazards and oscillations that may occur in the presence of
    gate and wire delays. Ternary simulation, introduced by Eichelberger in
    1965, consists of two algorithms, called A and B, and its results are
    well understood. Ternary simulation has been generalized by Brzozowski
    and Ésik in 2003 to an infinite algebra $C$ and finite algebras $C_k$,
    $k\geq 2$, where $C_2$ is ternary algebra. Simulation in $C$ has been
    studied extensively for feedback-free circuits, for which Algorithm A
    always terminates and Algorithm B is unnecessary. We study the
    simulation of gate circuits with feedback in finite algebras $C_k$, in
    which Algorithms A and B always terminate. The Boolean functions of the
    gates are restricted to a set $G$, where $G=H\cup\widetilde{H}$,
    $H=\{\mathrm{OR}, \mathrm{XOR}\}$, and $\widetilde{H}$ is the set of
    functions obtained by complementing any number of inputs and/or the
    output of functions from $H$. This set $G$ includes all the nontrivial
    1- and 2-variable functions and multi-input AND, OR, NAND, NOR, XOR and
    XNOR functions. We introduce a simple graph-theoretic model of a
    circuit. We derive new properties of extensions of Boolean functions to
    Algebra $C$. We prove that Algorithm B in Algebra $C_k$, for $k>2$,
    provides no more information than Algorithm B in ternary algebra. Thus,
    for any gate in any circuit, the final result of Algorithm B is always
    one of the binary values, 0 or 1, which are considered ‘certain’,
    or the third ‘uncertain’ value; the remaining values of $C_k$ never
    appear. This permits us to replace Algorithm B in $C_k$ by the same
    algorithm in ternary algebra, and to reduce the simulation time.
rv: