Component Refinement and CSC Solving for STG Decomposition

published 2004 in: Augsburg, Germany Technical Report, Institute of Computer Science, University of Augsburg, 2004

STGs give a formalism for the description of asynchronous circuits based on Petri nets. To overcome the state explosion problem one may encounter during circuit synthesis, a nondeterministic algorithm for decomposing STGs was suggested by Chu and improved by one of the present authors.

In this paper it is studied how CSC solving (which is essential for circuit synthesis) can be combined with decomposition. For this purpose the correctness definition for decomposition is enhanced with internal signals and it is shown that speed-independent CSC solving preserves correctness. The latter uses a more general result about correctness of top-down decomposition. Furthermore, we apply our definition to give the first correctness proof for the decomposition method of Carmona and Cortadella.

Keywords: STG, system decomposition, CSC, implementation relation, speed-independent

Downloads:

• Component Refinement and CSC Solving for STG Decomposition  -  (2004-13.pdf, 263 KB)