SIMULATION OF FEEDBACK-FREE CIRCUITS IN THE ALGEBRA OF TRANSIENTS
Mihaela Gheorghiu, Janusz Brzozowski · International Journal of Foundations of Computer Science · 2003
An efficient simulation algorithm using an algebra of transients for gate circuits was proposed by Brzozowski and Ésik. This algorithm seems capable of predicting all the signal changes that can occur in a circuit under worst-case delay conditions. We verify this claim by comparing simulation with binary analysis. For any feedback-free circuit consisting of one- and two-input gates, we prove that all signal changes predicted by simulation occur in binary analysis, provided that wire delays are taken into account. Two types of finite automata play an important role in our proof.