Affiliations: Institut für Informatik, Technische
Universität München, Germany. esparza@in.tum.de | Center of Applied Cybernetics, Dept of CS, TU Ostrava,
Czechia. Petr.Jancar@vsb.cz | Institute for Formal Methods in Computer Science,
Univ. Stuttgart, Germany. Alexander.Miller@informatik.uni-stuttgart.de
Note: [] Address for correspondence: Institut für Informatik,
Technische Universität München, Germany
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.
Keywords: signal transition graphs, consistency, complete state coding, Petri nets, complexity
