The Complexity of Synthesizing nop-Equipped Boolean Nets from g-Bounded Inputs (Technical Report)

Abstract

Boolean Petri nets equipped with nop allow places and transitions to be independent by being related by nop. We characterize for any fixed natural number g the computational complexity of synthesizing nop-equipped Boolean Petri nets from labeled directed graphs whose states have at most g incoming and at most g outgoing arcs.

Cited by in corpus (2)

• The Complexity of Boolean State Separation (Technical Report)
• On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency (Technical Report)