Title: The Hardness of Synthesizing Elementary Net Systems from Highly Restricted Inputs,
Abstract: Elementary net systems (ENS) are the most fundamental class of Petri nets.
Their synthesis problem has important applications in the design of digital
hardware and commercial processes. Given a labeled transition system (TS) $A$,
feasibility is the NP-complete decision problem whether $A$ can be equivalently
synthesized into an ENS. It is well known that $A$ is feasible if and only if
it has the event state separation property (ESSP) and the state separation
property (SSP). Recently, these properties have also been studied individually
for their practical implications. A fast ESSP algorithm, for instance, would
allow applications to at least validate the language equivalence of $A$ and a
synthesized ENS. Being able to efficiently decide SSP, on the other hand, could
serve as a quick-fail preprocessing mechanism for synthesis. Although a few
tractable subclasses have been found, this paper destroys much of the hope that
many practically meaningful input restrictions make feasibility or at least one
of ESSP and SSP efficient. We show that all three problems remain NP-complete
even if the input is restricted to linear TSs where every event occurs at most
three times or if the input is restricted to TSs where each event occurs at
most twice and each state has at most two successor and two predecessor states.