Title :
A polynomial-time algorithm for checking consistency of free-choice signal transition graphs
Author_Institution :
Inst. for Formal Methods in Comput. Sci., Stuttgart Univ., Germany
Abstract :
Signal transition graphs (STGs) are one of the most popular models for the specification of asynchronous circuits. A STG can be implemented if it admits a so-called consistent and complete binary encoding. Checking this is EXPSPACE-hard for arbitrary STGs, and so a lot of attention has been devoted to the subclass of free-choice STGs, which offers a good compromise between expressive power and analyzability. In the last years, polynomial time synthesis techniques have been developed for free-choice STGs, but they assume that the STG has a consistent binary encoding. The first polynomial algorithm for checking consistency is presented here.
Keywords :
Petri nets; asynchronous circuits; computational complexity; formal specification; logic CAD; EXPSPACE-hardness; asynchronous circuit; binary encoding; consistency checking; free choice signal transition graph; polynomial time algorithm; Algorithm design and analysis; Asynchronous circuits; Circuit synthesis; Clocks; Computer science; Encoding; Energy consumption; Petri nets; Polynomials; Signal synthesis;
Conference_Titel :
Application of Concurrency to System Design, 2003. Proceedings. Third International Conference on
Print_ISBN :
0-7695-1887-7
DOI :
10.1109/CSD.2003.1207700
