Reference:

J. Esparza, P. Jančar, and A. Miller. On the complexity of consistency and complete state coding for signal transition graphs. Fundamenta Informaticae, 86(3):227–253, 2008.

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.

Suggested BibTeX entry:

@article{JEM06c,
    author = {J. Esparza and P. Jan\v{c}ar and A. Miller},
    journal = {Fundamenta Informaticae},
    number = {3},
    pages = {227--253},
    title = {On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs},
    volume = {86},
    year = {2008}
}