A polynomial-time algorithm for checking consistency of free-choice signal transition graphs

Author

Esparza, Javier

Author_Institution

Inst. for Formal Methods in Comput. Sci., Stuttgart Univ., Germany

fYear

2003

Firstpage

61

Lastpage

70

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Application of Concurrency to System Design, 2003. Proceedings. Third International Conference on

Print_ISBN

0-7695-1887-7

Type

conf

DOI

10.1109/CSD.2003.1207700

Filename

1207700