loading...
A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs
Guimar?es, Portugal June 18-June 20
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CSD.2003.1207700Third International Conference on App ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Javier Esparza, "A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs," Application of Concurrency to System Design, International Conference on, pp. 61, Third International Conference on Application of Concurrency to System Design (ACSD'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/CSD.2003.1207700,
author = {Javier Esparza},
title = {A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs},
journal ={Application of Concurrency to System Design, International Conference on},
volume = {0},
year = {2003},
isbn = {0-7695-1887-7},
pages = {61},
doi = {http://doi.ieeecomputersociety.org/10.1109/CSD.2003.1207700},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Application of Concurrency to System Design, International Conference on
TI - A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs
SN - 0-7695-1887-7
SP
EP
A1 - Javier Esparza,
PY - 2003
KW - null
VL - 0
JA - Application of Concurrency to System Design, International Conference on
ER -
 
Javier Esparza, University of Stuttgart
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.
Citation:
Javier Esparza, "A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs," acsd, pp.61, Third International Conference on Application of Concurrency to System Design (ACSD'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.