Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 227-253 |
| Number of pages | 27 |
| Journal | Fundamenta Informaticae |
| Volume | 86 |
| Issue number | 3 |
| State | Published - 2008 |
Keywords
- Complete state coding
- Complexity
- Consistency
- Petri nets
- Signal transition graphs
Fingerprint
Dive into the research topics of 'On the complexity of consistency and complete state coding for signal transition graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver