Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T11:13:59.569Z Has data issue: false hasContentIssue false

Gate circuits in the algebra of transients

Published online by Cambridge University Press:  15 March 2005

Janusz Brzozowski
Affiliation:
School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada; brzozo@uwaterloo.ca
Mihaela Gheorghiu
Affiliation:
Department of Computer Science, University of Toronto, Toronto, ON, M5S 3G4, Canada; mg@cs.toronto.edu
Get access

Abstract


We study simulation of gate circuits in the infinite algebra oftransients recently introduced by Brzozowski and Ésik. A transientis a word consisting of alternating 0s and 1s; it represents achanging signal. In the algebra of transients, gates processtransients instead of 0s and 1s. Simulation in this algebra iscapable of counting signal changes and detecting hazards. We studytwo simulation algorithms: a general one that works with any initialstate, and a special one that applies only if the initial state isstable. We show that the two algorithms agree in the stable case. Wealso show that the general algorithm is insensitive to the removal ofstate variables that are not feedback variables. We prove thesufficiency of simulation: all signal changes occurring in binaryanalysis are predicted by the general algorithm. Finally, we showthat simulation can be more pessimistic than binary analysis, if wiredelays are not taken into account. We propose a circuit model that weconjecture to be sufficient for proving the equivalence of simulationand binary analysis for feedback-free circuits.


Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable