loading...
On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs
Turku, Finland June 28-June 30
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ACSD.2006.17Sixth International Conference on App ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy 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, Petr Jan?car, Alexander Miller, "On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs," Application of Concurrency to System Design, International Conference on, pp. 47-56, Sixth International Conference on Application of Concurrency to System Design (ACSD'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/ACSD.2006.17,
author = {Javier Esparza and Petr Jan?car and Alexander Miller},
title = {On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs},
journal ={Application of Concurrency to System Design, International Conference on},
volume = {0},
year = {2006},
issn = {1550-4808},
pages = {47-56},
doi = {http://doi.ieeecomputersociety.org/10.1109/ACSD.2006.17},
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 - On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs
SN - 1550-4808
SP47
EP56
A1 - Javier Esparza,
A1 - Petr Jan?car,
A1 - Alexander Miller,
PY - 2006
KW - null
VL - 0
JA - Application of Concurrency to System Design, International Conference on
ER -
 
Javier Esparza, Univ. Stuttgart, Germany
Petr Jan?car, TU Ostrava, Czechia
Alexander Miller, Univ. Stuttgart, Germany
Signal Transition Graphs (STGs) are a popular formalism for the specification of asynchronous circuits. A necessary condition for the implementability of an STG is the existence of a consistent and complete state encoding. For an important subclass of STGs, the marked graph STGs, we show that checking consistency is polynomial, but checking the existence of a complete state coding is co-NP-complete. In fact, co-NP-completeness already holds for acyclic and 1-bounded marked graph STGs and for live and 1-bounded marked graph STGs. We add some relevant results for freechoice, bounded, and general STGs.
Citation:
Javier Esparza, Petr Jan?car, Alexander Miller, "On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs," acsd, pp.47-56, Sixth International Conference on Application of Concurrency to System Design (ACSD'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions