English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Elementary net systems (ENS) are the most fundamental class of Petri nets.Their synthesis problem has important applications in the design of digitalhardware and commercial processes. Given a labeled transition system (TS) $A$,feasibility is the NP-complete decision problem whether $A$ can be equivalentlysynthesized into an ENS. It is well known that $A$ is feasible if and only ifit has the event state separation property (ESSP) and the state separationproperty (SSP). Recently, these properties have also been studied individuallyfor their practical implications. A fast ESSP algorithm, for instance, wouldallow applications to at least validate the language equivalence of $A$ and asynthesized ENS. Being able to efficiently decide SSP, on the other hand, couldserve as a quick-fail preprocessing mechanism for synthesis. Although a fewtractable subclasses have been found, this paper destroys much of the hope thatmany practically meaningful input restrictions make feasibility or at least oneof ESSP and SSP efficient. We show that all three problems remain NP-completeeven if the input is restricted to linear TSs where every event occurs at mostthree times or if the input is restricted to TSs where each event occurs atmost twice and each state has at most two successor and two predecessor states.

The Hardness of Synthesizing Elementary Net Systems from Highly Restricted Inputs