For the most recent entries see the Petri Nets Newsletter.

A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs.

Esparza, Javier

In: Third International Conference on Application of Concurrency to System Design (ACSD'03), Guimar„es, Portugal, pages 61-70. IEEE, June 2003.

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 analizability. 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. This paper presents the first polynomial algorithm for checking consistency.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography