@inproceedings{d7e417c781474faa872d45c60202da33,
title = "A polynomial-time algorithm for checking consistency of free-choice signal transition graphs",
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 = "Algorithm design and analysis, Asynchronous circuits, Circuit synthesis, Clocks, Computer science, Encoding, Energy consumption, Petri nets, Polynomials, Signal synthesis",
author = "Javier Esparza",
note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 3rd International Conference on Application of Concurrency to System Design, ACSD 2003 ; Conference date: 18-06-2003 Through 20-06-2003",
year = "2003",
doi = "10.1109/CSD.2003.1207700",
language = "English",
series = "Proceedings - International Conference on Application of Concurrency to System Design, ACSD",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "61--70",
editor = "Felice Balarin and Machado, {Ricardo J.} and Johan Lilius",
booktitle = "Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003",
}
