On the complexity of consistency and complete state coding for signal transition graphs

Javier Esparza, Petr Janar, Alexander Miller

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)227-253
Number of pages27
JournalFundamenta Informaticae
Volume86
Issue number3
StatePublished - 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