Improved Decomposition of Signal Transition Graphs

Issue title: The Fourth Special Issue on Applications of Concurrency to System Design (ACSD05)

Article type: Research Article

Authors: Vogler, W. | Kangsah,

Affiliations: Institut für Informatik, Universität Augsburg, Germany. E-mail: [email protected] | FB Elektro- und Informationstechnik, Technische Universität Kaiserlautern, Germany. E-mail: [email protected]

Abstract: Signal Transition Graphs (STGs) are a version of Petri nets for the specification of asynchronous circuit behaviour. It has been suggested to decompose such a specification as a first step; this leads to a modular implementation, which can support circuit synthesis by possibly avoiding state explosion or allowing the use of library elements. In a previous paper, the originalmethod was extended and shown to bemuchmore generally applicable than known before. But further extensions are necessary, and some are presented in this paper. In particular, to avoid dynamic auto-conflicts, the previous paper insisted on avoiding structural autoconflicts, which is too restrictive; as a main contribution, we show how to work with the latter type of auto-conflicts. This extension makes it necessary to restructure presentation and correctness proof of the decomposition algorithm.

Keywords: concurrent systems, Petri nets, asynchronous circuits, Signal Transition Graphs, decomposition, modular implementation, state explosion

Journal: Fundamenta Informaticae, vol. 78, no. 1, pp. 161-197, 2007