Correspondence between ternary simulation and binary race analysis in gate networks. (English) Zbl 0594.94031
Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 69-78 (1986).
Summary: [For the entire collection see Zbl 0587.00019.]
Ternary simulation techniques provide efficient methods for the analysis of the behavior of VLSI circuits. However, the results of ternary simulation have not been completely characterized. In this paper we outline the proof of the Brzozowski-Yoeli conjecture [J. A. Brzozowski and M. Yoeli, IEEE Trans. Comput. C-28, 178-184 (1979; Zbl 0408.94023)] that the results of the ternary simulation of a gate network N correspond to the results of the binary race analysis of \(\tilde N\) in the ”multiple-winner” model, where \(\tilde N\) is the network N in which a delay has been inserted in each wire.
Ternary simulation techniques provide efficient methods for the analysis of the behavior of VLSI circuits. However, the results of ternary simulation have not been completely characterized. In this paper we outline the proof of the Brzozowski-Yoeli conjecture [J. A. Brzozowski and M. Yoeli, IEEE Trans. Comput. C-28, 178-184 (1979; Zbl 0408.94023)] that the results of the ternary simulation of a gate network N correspond to the results of the binary race analysis of \(\tilde N\) in the ”multiple-winner” model, where \(\tilde N\) is the network N in which a delay has been inserted in each wire.
MSC:
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
