Affiliations: School of Computing Science, Newcastle University, UK.
victor.khomenko@ncl.ac.uk | Institute of Computer Science, University of Augsburg,
Germany. {mark.schaefer, walter.vogler}@informatik.uni-augsburg.de
Note: [] Address for correspondence: Institut für
Informatik, 86135 Augsburg, Germany
Abstract: Signal Transition Graphs (STG) are a formalism for the description
of asynchronous circuit behaviour. In this paper we propose (and justify) a
formal semantics of non-deterministic STGs with dummies and OR-causality. For
this, we introduce the concept of output-determinacy, which is a relaxation of
determinism, and argue that it is reasonable and useful in the
speed-independent context. We apply the developed theory to improve an STG decomposition
algorithm used to tackle the state explosion problem during circuit synthesis,
and present some experimental data for this improved algorithm and some
benchmark examples.
