On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F06%3A00021177" target="_blank" >RIV/61989100:27240/06:00021177 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs
Original language description
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 free-choice, bounded, and general STGs.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0567" target="_blank" >1M0567: Centre for Applied Cybernetics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Fundamenta Informaticae
ISBN
—
ISSN
0169-2968
e-ISSN
—
Number of pages
10
Pages from-to
—
Publisher name
IOS Press
Place of publication
Amsterodam
Event location
Turku, Finland
Event date
Jun 28, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000262367600002