|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 6 gevonden artikelen
| Titel: |
On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs |
| Auteur: |
Esparza, Javier Jančar, Petr Miller, Alexander |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 86 (2008) nr. 3 pagina's 227-253 |
| Jaar: |
2008-12-16 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 6 gevonden artikelen
| << vorige | volgende >> |