Parameterized Complexity of Synthesizing b-Bounded (m, n)-T-Systems

Abstract

Let $b\in \mathbb {N}^+$. Synthesis of pure b-bounded (m, n)-T-systems ((m,n)-Synthesis, for short) consists in deciding whether there exists for an input (A, m, n) of transition system A and integers $m,n\in \mathbb {N}$ a pure b-bounded Petri net N as follows: N’s reachability graph is isomorphic to A, and each of N’s places has at most m incoming and at most n outgoing transitions. In the event of a positive decision, N should be constructed. The problem is known to be NP-complete, and (m,n)-Synthesis parameterized by $m+n$ is in XP [14]. In this paper, we enhance our understanding of (m,n)-Synthesis from the viewpoint of parameterized complexity by showing that it is W[1]-hard when parameterized by $m+n$.

1 Introduction

Petri net synthesis consists in deciding whether there is a Petri net (PN, for short) that implements a given behavioral specification and in constructing such a net if it exists. Valid synthesis methods yield implementations that are correct by design. The possibility of finding effective or even efficient synthesis algorithms crucially depends on the specification and the searched net. This has been subject of research for many years: It is undecidable whether there is a P/T net implementing a pushdown- or a HMSC-language or whether there is a (pure) bounded P/T net implementing a modal transition systems (MTS, for short) [9, 11]. If the specification is a deterministic pushdown-language or -graph, and the search net is a P/T-net, synthesis is decidable [4]. It is also decidable whether there is a b-bounded Petri net that implements an MTS [12]. If the specification is a transition system (TS, for short), and the searched net is a 1-bounded PN, synthesis is NP-complete [2], even if the TS is strongly restricted [15, 16]. The synthesis of b-bounded PNs from TSs is NP-complete, even if the searched net is strongly restricted [13, 14]. If the bound b is not fixed in advance, the synthesis of bounded PN from TSs is polynomial [1]. If the PN is additionally to be choice-free or a marked graph, even better procedures exist [5, 7].

In this paper, we investigate an instance of PN synthesis that is called (m, n)-Synthesis. It consists in deciding whether there exists for an input (A, m, n) of TS A and integers $m,n\in \mathbb {N}$ a pure b-bounded Petri net N as follows: N’s reachability graph is isomorphic to A, and each of N’s places has at most m incoming and at most n outgoing transitions. The b-bounded (m, n)-T-systems generalize the notion of (weighted) T-systems [6, 10] and adapt it to b-bounded PN. In [14], we have shown that (m, n)-Synthesis is NP-complete. We have also argued that (m, n)-Synthesis parameterized by $m+n$ belongs to the complexity class XP. Thus, the question arises whether this parameterization makes the problem fixed parameter tractable. In this paper, we answer this question negatively and show that (m, n)-Synthesis parameterized by $m+n$ is W[1]-hard. The proof presents a parameterized reduction from regular independent set, which restricts the canonical W[1]-hard problem to regular graphs [8], to (m, n)-Synthesis. This paper is organized as follows. Section 2 introduces necessary preliminary notions, Sect. 3 presents the W[1]-hardness result and Sect. 4 closes the paper.

2 Preliminaries

We assume that the reader is familiar with the concepts relating to fixed-parameter tractability, the standard notions relating to graphs and Regular Independent Set, the canonical W[1]-hard problem restricted to regular graphs. Due to space restrictions, we omit some formal definitions and some proofs. See [8] for the definitions of relevant notions in parameterized complexity theory. In the remainder of this paper, if not stated explicitly otherwise, then $b\in \mathbb {N}^+$ is assumed to be arbitrary but fixed.

Transition Systems. A transition system (TS, for short) $A=(S,E,\delta , \iota )$ consists of a finite disjoint set S of states, E of events, a partial transition function $\delta : S\times E\rightarrow S$ and an initial state $\iota \in S$. A TS A is interpreted as edge-labeled directed graph, and every triple $\delta (s,e)=s'$ is considered an e-labeled edge , called transition. An event e occurs at state s, denoted by , if $\delta (s,e)=s'$ for some state $s'$. This notation is extended to words $w'=we$, $w\in E^*, e\in E$, by inductively defining for all $s\in S$ and if and only if there is a state $s'\in S$ satisfying and . If $w\in E^*$, then denotes that there is a state $s'\in S$ such that . If $e\in E$, then by we denote that there are distinct states $s_i,s_{i+1},\dots , s_{i+b-1}, s_{i+b}\in S$ such that . We assume all TSs to be reachable: .

b-Bounded Petri Nets. A b-bounded Petri net (b-net, for short) $N=(P,T,f,M_0)$ consists of finite and disjoint sets of places P and transitions T, a (total) flow function $f: P \times T\rightarrow \{0,\dots , b\}^2$ and an initial marking $M_0: P \rightarrow \{0,\dots , b\}$. If $f(p,t)=(m,n)$, then $f^-(p,t)=m$ and $f^+(p,t)=n$ define the consuming and the producing effect of t on p, respectively. The preset of a place p is defined by $\,^{\!\bullet }p=\{t\in T \mid f^+(p,t)>0\}$ (transitions producing on p) and its postset is defined by $p^{\bullet } =\{t\in T \mid f^-(p,t)>0\}$ (transitions consuming from p). Accordingly, the preset of a transition t is defined by $\,^{\!\bullet }t=\{ p\in P \mid f^-(p,t)>0\}$ (places from which t consumes) and its postset by $t^{\bullet } =\{p\in P \mid f^+(p,t)>0\}$ (places on which t produces). A b-net N is pure if $\forall (p,t) \in P \times T: f^-(p,t)=0 \text { or } f^+(p,t) =0$, that is, $\forall p\in P: \,^{\!\bullet }p \cap p^{\bullet }=\emptyset$. Let $m,n\in \mathbb {N}$. A b-net N is an (m, n)-T-system if $\forall p\in P: \vert \,^{\!\bullet }p \vert \le m, \vert p^{\bullet } \vert \le n$.The firing rule of b-nets defines their behavior: A transition $t\in T$ can fire or occur in a marking $M:P\rightarrow \{0,\dots ,b\}$, denoted by , if $M(p)\ge f^-(p,t)$ and $M(p)-f^-(p,t)+f^+(p,t) \le b$ for all places $p\in P$. The firing of t in marking M leads to the marking $M'$ if $M'(p)=M(p)-f^-(p,t)+f^+(p,t)$ for all $p\in P$. This is denoted by . Again, this notation extends to sequences $\sigma \in T^*$, and the reachability set contains N’s reachable markings. The firing rule preserves N’s b-boundedness by definition: $M(p) \le b$ for all $p\in P$ and all $M\in RS(N)$. The reachability graph of N is the TS $A_N=(RS(N), T,\delta , M_0)$, such that for all $M, M'\in RS(N)$ and all $t\in T$ we define $\delta (M,t) = M'$ if and only if .

b-Bounded Regions. To find a b-net N implementing a TS A, we want to synthesize N’s components purely from the input A. Since A and $A_N$ are to be isomorphic, A’s events correspond to N’s transitions. However, the notion of a place is not known for TSs. A b-bounded region R (region, for short) of a TS $A=(S,E,\delta ,s_0)$ is a pair $R=(sp, sg)$ of support $sp: S\rightarrow \{0,\dots , b\}$ and signature $sg: E\rightarrow \{0,\dots , b\}^2$ such that for every edge of A holds $sp(s)\ge sg^-(e)$ and $sp(s')=sp(s)-sg^-(e)+sg^+(e)$. If $sg(e)=(m,n)$, then $sg^-(e)=m$ and $sg^+(e)=n$ define e’s consuming and producing effect (concerning R), respectively.

A region (sp, sg) models a place p and the corresponding part of the flow function f: $sg^+(e)$ models $f^+(e)$, $sg^-(e)$ models $f^-(e)$ and sp(s) models M(p) in the marking $M\in RS(N)$ corresponding to $s\in S(A)$. The preset of R is defined by the producing events $\,^{\!\bullet }R=\{e\in E \mid sg^+(e) > 0\}$ and its postset by the consuming events $R^{\bullet } =\{e\in E \mid sg^-(e) > 0\}$. If $sg(e)=(0,0)$, then e is called neutral. The region R is pure if $\,^{\!\bullet }R \cap R^{\bullet } =\emptyset$. Let $\mathcal {R}$ be a set of regions of A, and let $e\in E$. By $\,^{\!\bullet }e_{\mathcal {R}}=\{(sp, sg)\in \mathcal {R} \mid sg^-(e)>0 \}$ and $e_{\mathcal {R}}^{\bullet } =\{(sp, sg) \in \mathcal {R} \mid sg^+(e)>0 \}$ we define the preset and postset of e (concerning $\mathcal {R}$), respectively. The set $\mathcal {R}$ defines the synthesized b-net $N^{\mathcal {R}}_A=(\mathcal {R}, E, f, M_0)$ with flow function $f((sp, sg),e)=sg(e)$ and initial marking $M_0((sp, sg))=sp(s_{0})$ for all $(sp, sg)\in \mathcal {R}, e\in E$. We emphasize again that a region R of $\mathcal {R}$ is a place of $N^{\mathcal {R}}_A$ with the preset $\,^{\!\bullet }R$ and the postset $R^{\bullet }$; every event $e\in E$ is a transition of $N^{\mathcal {R}}_A$ with preset $\,^{\!\bullet }e = \,^{\!\bullet }e_\mathcal {R}$ and postset $e^{\bullet } = e_\mathcal {R}\!^{\bullet }$. It is well known that $A_{N^{\mathcal {R}}_A }$ and A are isomorphic if and only if $\mathcal {R}$’s regions solve certain separation atoms [3], to be introduced next.

A pair $(s, s')$ of distinct states of A defines a state separation atom (SSP atom, for short). A region $R=(sp, sg)$ solves $(s,s')$ if $sp(s)\not =sp(s')$. The region R is to ensure that $N^{\mathcal {R}}_A$ contains at least one place R such that $M(R)\not =M'(R)$ for the markings M and $M'$ corresponding to s and $s'$, respectively. If there is a b-region that solves $(s,s')$, then s and $s'$ are called b-solvable (solvable, for short). If every SSP atom of A is solvable, then A has the b-state separation property (SSP for short). If $e\in E$ and $s\in S$ such that e does not occur at s (), then the pair (e, s) is an event state separation atom (ESSP atom, for short). A b-region $R=(sp, sg)$ solves (e, s) if $sg^-(e) > sp(s)$ or $sp(s)-sg^-(e)+sg^+(e)>b$. The meaning of R is to ensure that there is at least one place R in $N^{\mathcal {R}}_A$ such that for the marking M corresponding to s. If there is a region that solves (e, s), then e and s are called b-solvable; we also say e is solvable at s. If every ESSP atom of A is b-solvable, then A has the b-event state separation property (ESSP, for short).

A set $\mathcal {R}$ of regions of A is called b-admissible if for every of A’s (E)SSP atoms there is a region R in $\mathcal {R}$ that solves it. The following lemma, borrowed from [3, p. 163], summarizes the connection between b-admissible sets of A and synthesis:

Lemma 1

([3]). A b-net N has a reachability graph isomorphic to a given TS A if and only if there is a b-admissible set $\mathcal {R}$ of A such that $N=N^{\mathcal {R}}_A$.

We say a b-net N solves A if $A_N$ and A are isomorphic. By Lemma 1, searching for a restricted b-net reduces to finding a b-admissible set of accordingly restricted regions. The following example illustrates this fact.

Example 1

Let $m,n\in \mathbb {N}$, A be a TS and $\mathcal {R}$ be a b-admissible set of pure regions of A. If every region $R\in \mathcal {R}$ satisfies $\vert \,^{\!\bullet }R \vert \le m$ and $\vert R^{\bullet } \vert \le n$, then $N^{\mathcal {R}}_A$ is a pure (m, n)-T-system solving A. In particular, if $b=2$, then the TS has the following pure regions:

The set $\mathcal {R}=\{(sp_i,sg_i)\mid 1\le i\le 4 \}$ is 2-admissible. Since $\,^{\!\bullet }(sp_4, sg_4)=\{e_1,e_2\}$, the solving 2-net $N^{\mathcal {R}}_A$ is not a (1, 1)-T-system. However, the set $\mathcal {R'}=\{(sp_i,sig_i)\mid 1\le i\le 3 \}$ is 2-admissible, and $N^{\mathcal {R'}}_A$ is a (1, 1)-T-system solving A.

3 W[1]-Hardness Parameterized by $m+n$

This section is dedicated to the proof of our main result:

Theorem 1

(m, n)-Synthesis parameterized by $m+n$ is W[1]-hard.

The proof of Theorem 1 consists of a parameterized reduction of Regular Independent Set to (m, n)-Synthesis. Let (G, k) be an instance of Regular Independent Set. That is, $G=(V(G), E(G))$ is a graph with set of nodes $V(G)=\{v_1,\dots , v_n\}$, set of edges $E(G)=\{a_1,\dots , a_m\}$, and there is an integer $r\in \mathbb {N}$ such that for every node $v\in V(G)$ holds $\vert \{e\in E(G)\mid v\in e\}\vert =r$, and k is a positive integer. We reduce (G, k) to an instance $(A, 2rk+20, 2rk+20)$ of (m, n)-Synthesis, parameterized by $m+n$, such that G has a k-independent set if and only if A is solvable by a $(2rk+20, 2rk+20)$-T-system.

To represent G, the TS A has for every edge $a_i=\{v_{i,1}, v_{i,2}\}$, $i\in \{1,\dots , m\}$, the following gadget $G_i$, which uses $a_i, v_{i,1}$ and $v_{i,2}$ as events:

Let $i\in \{1,\dots , m\}$. The proof of the if-direction bases on the idea to ensure that if A is solvable, then there is a pure region $R=(sp, sg)$ that satisfies the following conditions. Firstly, $sg(\alpha _1)=(b,0)$, which implies $sp(g_{i,2})=b$. Secondly, the producing effect of the node events is zero, that is, $sg^+(v_{i,1})=sg^+(v_{i,2})=0$. Thirdly, the $\zeta$-events are neutral, that is, $sg(\zeta ^1_{i,1})=sg(\zeta ^1_{i,2})=sg(\zeta ^1_{i,3})=(0,0)$. As a result, the support value of $g_{i,2b+5}$ is given by $sp(g_{i,2b+5})=b-b \cdot (sg^-(v_{i,1}) + sg^-(v_{i,2}))$. Moreover, if $sp(g_{i,2b+5}) < b$, then there is exactly one $e\in \{v_{i,1}, v_{i,2}\}$ such that $sig^-(e)>0$. Otherwise we would have the contradiction $sp(g_{i,2b+5}) < 0$. Furthermore, the region R ensures that there are exactly rk edge events with a positive producing effect. That is, there are exactly rk indices $i_1,\dots , i_{rk}\in \{1,\dots , m\}$ such that $sg^+(a_{i_j})>0$ for all $j\in \{1,\dots , rk\}$. Since R is pure, this implies $sg^-(a_{i_j})=0$ for all $j\in \{1,\dots , rk\}$. Moreover, by , we obtain $sup(g_{i_j,2b+6})= sup(g_{i_j,2b+5}) + sig^+(a_{i_j})$. This requires $sp(g_{i_j,2b+5}) < b$, and exactly one of $v_{i_j,1}$ and $v_{i_j,2}$ has a positive consuming effect. The region R ensures that there are exactly k node events $v_{\ell _1},\dots , v_{\ell _k}$ with a positive consuming effect. Recall, for every node $v\in V(G)$ holds $\vert \{e\in E(G)\mid v\in e\}\vert = r$. Thus, if $v_{\ell _1},\dots , v_{\ell _k}$ are not independent, then the number of edges which are adjacent to a node of $v_{\ell _1},\dots , v_{\ell _k}$ is at most $rk-1$. Since rk edge events have a positive producing effect, and each of it needs a consuming node, this is a contradiction. Consequently, the set $I=\{v\in V(G) \mid sg^-(v)>0\}$ defines a k-independent set of G.

For the only-if-direction we show that if G has a k-independent set then there is a b-admissible set of regions $\mathcal {R}$ such that $\vert \,^{\!\bullet }R\vert , \vert R^{\bullet }\vert \le 2rk+20$ for all $R\in \mathcal {R}$. The major challenge here is to keep the number of consuming and producing events of solving regions smaller than the parameter. To do so, we exploit G’s regularity and the $\delta$- and $\zeta$-events. In what follows, we prove the following lemma:

Lemma 2

• 1. If A is solvable, then there is a region (sp, sg) such that the following conditions are true:

  • (a) $sg(\alpha _1)=(b,0)$ and $sg(\zeta ^1_{i,1})=\dots =sg(\zeta ^1_{i,3})=(0,0)$ for all $i\in \{1,\dots , m\}$.

  • (b) If $e\in \{a_1,\dots , a_m\}$ then $sg^-(e)=0$ and there are exactly rk events $a_{i_1},\dots , a_{i_{rk}}\in \{a_1,\dots , a_m\}$ with $sg^+(a_{i_j})>0$, where $j\in \{1,\dots , rk\}$.

  • (c) If $e\in \{v_1,\dots , v_n\}$ then $sg^+(e)=0$. Furthermore, there are exactly k events $v_{i_1},\dots , v_{i_{k}}\in \{v_1,\dots , v_n\}$ with $sg^-(v_{i_j})>0$ for all $j\in \{1,\dots , k\}$.

• 2. If G has an independent set of size k then there is a b-admissible set $\mathcal {R}$ of A such that $\vert \,^{\!\bullet }R\vert , \vert R^{\bullet }\vert \le 2rk+20$ for all $R\in \mathcal {R}$.

3.1 The Proof of Lemma 2.1

This section introduces the gadgets that ensure Lemma 2.1. For now, we refrain from explaining in which way they are actually conjunct to build A. This conjunction is postponed to Sect. 3.2, which is dedicated to Lemma 2.. We let events $e\in E(A)$ occur b times in row to restrict their possible signature in advance:

Lemma 3

Let A be a TS, and let $e\in E(A)$ be an event that occurs b times in a row: . For any pure region (sp, sg) of A with $sg^+(e)\not =sg^-(e)$ holds either $sg(e)=(1,0)$, $sp(s_1)=b$ and $sp(s_{b+1})=0$ or $sg(e)=(0,1)$, $sp(s_1)=0$ and $sp(s_{b+1})=b$.

Proof

The claim follows by $b\ge sp(s_{b+1})= sp(s_1) + b\cdot (sg^+(e) - sg^-(e))\ge 0$.

The TS A has for $i\in \{1,2,3\}$ the following w-maker gadget $X_i$:

If A is solvable, then there is a region $R=(sp, sg)$ that solves the atom $(\alpha , x_{1, b+3})$, that is, $sg^-(\alpha ) > sp(x_{1,b+3})$ or $sp(x_{1,b+3})-sg^-(\alpha ) + sg^+(\alpha ) > b$. This implies $sg(\alpha )\not =(0,0)$. Thus, by Lemma 3, we have $sg(\alpha )\in \{(1,0), (0,1)\}$. Since our arguments are symmetrically true for the case $sg(\alpha )=(0,1)$, we assume $sg(\alpha )=(1,0)$ and show that this implies a k-independent set of G.

Since R solves $(\alpha , x_{i, b+3})$, by $sg(\alpha )=(1,0)$, we conclude $sg^-(\alpha ) > sp(x_{i, b+3})=0$. Moreover, by Lemma 3, we obtain $sp(x_{i, b+2})=0$ and $sp(x_{i, b+4})=b$ for all $i\in \{1,2,3\}$. Furthermore, by $sp(x_{1, b+2})=sp(x_{1, b+3})=0$, we get $sg(\zeta )=(0,0)$. By $sp(x_{i, b+2})=0$, this implies $sp(x_{i, b+3})=0$ for all $i\in \{2,3\}$. Finally, by $sp(x_{i,b+3})=0$ and $sp(x_{i, b+4})=b$ for all $i\in \{1,2,3\}$, we get the three producing w-events $w_1,w_2,w_3$: $sg(w_1)=sg(w_2)=sg(w_3)=(0,b)$.

The TS A has for $i\in \{1,\dots , 9\}$ a so called $\alpha$-maker $Y_i$ that uses $w_1$ and $w_2$ to manipulate the support of some states and provides the consuming $\alpha$-event $\alpha _i$:

By $sg(w_1)=sg(w_2)=(0,b)$, we have $sp(y_{i,3})=b$ and $sp(y_{i,4})=0$. This implies $sg(\alpha _i)=(b,0)$ for $i\in \{1,\dots , 9\}$. The events $\alpha _1,\dots , \alpha _9$ are applied to manipulate the support of some states. For example, by $sg(\alpha _1)=(b,0)$ and , we have $sp(g_{i,2})=b$ for all $i\in \{1,\dots ,m\}$ as discussed before. The following $\beta$-makers also exemplify the functionality of the $\alpha$-events.

The TS A has for every $i\in \{1,\dots , 5\}$ the following $\beta$-maker $Z_i$ that uses the events $\alpha _7$ and $\alpha _8$ to provide the producing $\beta$-event $\beta _i$:

In particular, by $sg(\alpha _7)=sg(\alpha _8)=(b,0)$, we get $sp(z_{i,3})=0$ and $sp(z_{i,4})=b$. This implies $sg(\beta _i)=(0,b)$ for all $i\in \{1,\dots , 5\}$. Just like the $\alpha$-events, the $\beta$-events serve to manipulate the support of some states.

In the remainder of this section, we first introduce the gadgets ensuring that $R=(sp, sg)$ selects exactly rk edge events $a_{i_1},\dots , a_{i_{rk}}$ such that $sig^+(a_{i_j})>0$ for all $j\in \{1,\dots , rk\}$. Secondly, we introduce the gadgets that ensure that there are exactly k node events $v_{\ell _1},\dots , v_{\ell _k}$ such that $sig^-(v_{\ell _j})>0$ for all $j\in \{1,\dots , k\}$. Similar to the already presented gadgets $G_1,\dots , G_m$, these gadgets apply $\zeta$-events, that is, elements of the set $Z=\{\zeta ^i_{j,\ell }\mid i,j,\ell \in \mathbb {N}\}$. For the region R, corresponding to Lemma 2.1, these events have to be neutral. For the proof of Lemma 2. they allow solving regions with small preset- and postset-cardinality. If $\zeta ^i_{j,\ell } \in Z \cap E(A)$, that is, $\zeta ^i_{j,\ell }$ actually occurs in A, then A has the following $\zeta$-makers (left) and $\bigoplus ^i_{j,\ell }$ (right). These gadgets ensure $\zeta ^i_{j,\ell }$’s neutrality:

By $sg(w_3)=(0,b)$ and $sg(\alpha _9)=(b,0)$, we get $sp(\ominus ^i_{j,\ell ,2})=0$ and $sp(\oplus ^i_{j,\ell ,2})=b$. Moreover, by $0=sp(\ominus ^i_{j,\ell ,2}) \ge sg^-(\zeta ^i_{j,\ell })$, we obtain $sg^-(\zeta ^i_{j,\ell })=0$. Finally, by $b \ge sp(\oplus ^i_{j,\ell ,4})=sp(\oplus ^i_{j,\ell ,2}) - sg^-(\zeta ^i_{j,\ell }) + sg^+(\zeta ^i_{j,\ell })$, implying $b\ge b + sg^+(\zeta ^i_{j,\ell })$, we get $sg^+(\zeta ^i_{j,\ell })=0$.

So far, we have introduced A’s gadgets that yield us the $\alpha$-, $\beta$- and $\zeta$-events with the following behavior: If , then $sp(s)=b$; if , then $sp(s)=0$; if , then $sp(s)=sp(s')$. These events are applied in the subsequently introduced gadgets, which collaborate to provide the announced behavior of A.

The TS A has for every edge event $a_i$, $i\in \{1,\dots , m\}$, exactly rk edge copies (e-copies, for short) $a_i^1,\dots , a_i^{rk}$. These copies are used to enable the announced selection of rk edge events $a_{i_1},\dots , a_{i_{rk}}$. To achieve this goal, it is necessary that edge events do not consume and e-copies do not produce. The TS A has for every $i\in \{1,\dots , m\}$ an edge noCon $C_i$. This gadget ensures that $a_i$ does not consume. Moreover, for all $i\in \{1,\dots , m\}$ and all $j\in \{1,\dots , rk\}$ it has an e-copy noPro $D_{i,j}$. This gadget guarantees that $a^j_i$ does not produce.

By $sg(\beta _1)=(0,b)$ and $sg(\zeta ^2_{i,1})=(0,0)$, we have $sp(c_{i,3})=0$. Since $sp(c_{i,3}) \ge sg^-(a_i)$, this implies $sg^-(a_i)=0$. Similarly, by $sg(\alpha _2)=(b,0)$ and $sg(\zeta ^3_{i,j})=(0,0)$, we obtain $sp(d_{i,j,3})=b$. The region R is pure. Thus, if $sg^+(a^j_i)>0$ then $sg^-(a^j_i)=0$. This implies $sp(d_{i,j,4})=b+sg^+(a^j_i)> b$, a contradiction. Hence, $sg^+(a^j_i)=0$ is true.

The region R selects for every $j\in \{1,\dots , rk\}$ exactly one $i\in \{1,\dots , m\}$ such that the e-copy $a^j_i$ has a positive consuming effect, that is, $sig^-(a^j_i) >0$. The other e-copies remain neutral. To achieve this, the TS A uses for every $j\in \{1,\dots , rk\}$ the edge selector $F_j$. The gadget $F_j$ applies the events $a^j_1,\dots , a^j_m$, that is, the j-th copy of every edge event $a_1,\dots , a_m$. On $F_j$, every $a^j_i$ occurs b times consecutively. Separated by $\zeta$-events, these occurrences $(a^j_1)^b,\dots , (a^j_m)^b$ are placed in a sequence. We abridge $\ell =(m-1)(b+1)$ and define $F_j$:

By $sg(\alpha _3)=(b,0)$, we have $sp(f_{j,2})=b$ and, by $sg(\beta _2)=(0,b)$, we have $sp(f_{j,m(b+1)+3})=0$. The $\zeta$-events are neutral, and $sg^+(a^j_i)=0$ for all $i\in \{1,\dots , m\}$. Thus, we obtain $0=\sum ^{m}_{i=1} b\cdot sg^-(a^j_i) < b$. Consequently, there is an $i\in \{1,\dots , m\}$ such that $sg^-(a^j_i)=1$, and $sg^-(a^j_{i'})=0$ for all $i'\in \{1,\dots , m\}\setminus \{i\}$. The following edge connectors complete the set of A’s gadgets that allow the selection of rk edges $a_{i_1},\dots , a_{i_{rk}}$.

The TS A has for all $i\in \{1,\dots , m\}$ a so called edge connector $H_i$ whose purpose is twofold. On the one hand, it ensures that the edge selectors never choose two consuming copies of the same edge event, that is, if $j\not =j'$, $sg^-(a_i^j)>0$ and $sg^-(a^{j'}_{i'})>0$, then $i\not =i'$. On the other hand, $sg^+(a_i)>0$ if and only if there is a $j\in \{1,\dots , rk\}$ such that $sg^-(a^j_i)>0$. Since $F_1,\dots , F_{rk}$ select rk consuming edge copies, this picks out exactly rk edges $a_{i_1},\dots , a_{i_{rk}}$ with a positive producing effect. The gadget $H_i$ applies the event $a_i$ and its rk copies. Separated by $\zeta$-events, two sequences of $a_i$’s copies $a^1_i,\dots ,a^{rk}_{i}$, each of if it occurring b times consecutively, embrace the event $a_i$. For readability, we abridge $\ell =(b+1)rk+2$ and define $H_i$ as follows:

By $sg(\alpha _4)=(b,0)$ it is $sp(h_{i,2})=b$. The $\zeta$-events are neutral, and $sg^+(a^j_i)=0$ for all $j\in \{1,\dots , rk\}$. Thus, it is $sp(h_{(b+1)rk+3})=b-\sum ^{rk}_{j=1} b\cdot sg^-(a^j_i)$, and, by $sp(h_{(b+1)rk+3})\ge 0$, there is at most one $j\in \{1,\dots , rk\}$ such that $sg^-(a^j_i)>0$. Consequently, two copies of the same edge event are never selected by the edge selectors. By Lemma 3, if $sg^-(a^j_i)>0$, then $sg^-(a^j_i)=1$. This implies $sp(h_{(b+1)rk+3}) = 0$. Furthermore, $a^j_i$ occurs again b times in a row “after” the occurrence of $a_i$ at $h_{i, (rk+j-1)(b+1)+5}$. This implies $sp(h_{i, (rk+j-1)(b+1)+5})=b$. Since no edge copy produces, $sg(a_i)=(0,b)$ is immediately implied. Conversely, if $sg^+(a_i) > 0$, then $sp(h_{(b+1)rk+3}) < b$. Thus, by $sp(h_{(b+1)rk+3})=b-\sum ^{rk}_{j=1} b\cdot sg^-(a^j_i)$, there is a consuming copy of $a_i$. Consequently, $sg^+(a_i) > 0$ if and only if $sg(a_i)=(0,b)$ and there is exactly one $j\in \{1,\dots , rk\}$ such that $sg^-(a^j_i)=1$.

So far we have argued that there are exactly rk distinct indices $i_1,\dots , i_{rk}\in \{1,\dots , m\}$ such that $sg(a_{i_1})=\dots =sg(a_{i_{rk}})=(0,b)$. Moreover, $sg(a_{i})=(0,0)$ for all $i\in \{1,\dots , m\}\setminus \{i_1,\dots , i_{rk}\}$. It remains to argue that these rk “edges” $a_{i_1},\dots , a_{i_{rk}}$ are covered by exactly k “nodes”. To achieve this goal, the TS A uses gadgets that work symmetrically to the ones used for the selection of the edges. So called node noPros ensure that the node events $v_1,\dots , v_n$ do not produce. Moreover, the TS A applies for all $i\in \{1,\dots , n\}$ k node-copies $v^1_i,\dots , v^k_i$ and uses n-copy noCons to prevent them from consuming. Furthermore, node selectors force exactly k node copies to have a producing signature. The node connectors ensure that two copies of the same node are never selected and connects a producing node copy $v^j_i$ with its, then consuming, node event $v_i$. Finally, exactly k nodes $v_{\ell _1},\dots , v_{\ell _k}$ consume. Since these gadgets work symmetrically to the ones for the edges, we only briefly prove their functionality.

The TS A has for $i\in \{1,\dots , n\}$ the so called node noPro $P_i$ (left hand side) and for $i\in \{1,\dots , n\}$ and $j\in \{1,\dots , k\}$ the so called n-copy antiCon $Q_{i,j}$ (right hand side) which are defined as follows:

By $sg(\alpha _5)=(b,0)$ and $sg(\zeta ^6_{i,1})=(0,0)$, we get $sp(p_{i,3})=b$ which implies $sg^+(v_i)=0$. Moreover, by $sg(\beta _3)=(0,b)$ and $sg(\zeta ^7_{i,j})=(0,0)$, we get $sp(q_{i,j,3})=0$ which implies $sg^-(v^j_i)=0$.

The TS A has for every $j\in \{1,\dots , k\}$ a node selector $T_j$. On $T_j$, separated by $\zeta$-events, the j-th copy of every node event $v_1,\dots , v_n$ occurs b times in a row. We abridge $\ell =(n-1)(b+1)+2$ and define $T_j$ as follows:

By $sg(\beta _4)=(0,b)$, $sg(\alpha _6)=(b,0)$, the neutrality of the $\zeta$-events and $sg^-(v^j_1)=\dots =sg^-(v^j_n)=0$, we have $b = sp(t_{j,n(b+1)+3}) = \sum _{i=1}^n b \cdot sg^+(v^j_i) > sp(t_{j,3})=0$. Thus, there is exactly one producing j-th copy produces and others are neutral.

Finally, the TS A has for every $i\in \{1,\dots , n\}$ a so called node connector $U_i$ that, among others, applies the $\beta$-event $\beta _5$, the k copies $v^1_i,\dots , v^k_i$ of $v_i$ and the event $v_i$. We abridge $\ell =(k-1)(b+1)+2$ and define $U_i$ as follows:

By $sg(\beta _5)=(0,b)$, the neutrality of the $\zeta$-events and $sg^-(v^j_i)=0$ for all $j\in \{1,\dots , k\}$, it holds $b \ge sp(u_{j,k(b+1)+3}) = \sum _{j=1}^k b\cdot sg^+(v^j_i)$. Thus, at most one node-copy $v^j_i$, $j\in \{0,\dots , k\}$, of $v_i$ is not neutral. In particular, two copies of the same node are never selected by the node selectors. Moreover, if $sg^-(v_i) > 0$, then $sp(u_{j,k(b+1)+3}) > 0$. Consequently, if $v_i$ consumes, then there is a producing copy $v^j_i$. Since there are at most k producing node copies, there are at most k consuming nodes $v_{\ell _1},\dots , v_{\ell _{k}}$. Thus, the rk producing events $a_{i_1},\dots , a_{i_{rk}}$ are “covered” by exactly k consuming events $v_{\ell _1},\dots , v_{\ell _{k}}$. Altogether, this proves that $I=\{v\in V(G) \mid sg^-(v)>0\}$ defines an independent set of size k of G.

3.2 The Proof of Lemma 2.2

Table 1. The gadgets of A and their corresponding $\gamma$-events.

The reduction merges the introduced gadgets to a directed labelled binary tree with initial state $\iota =g_{1,1}$. The resulting TS A consists of 14 blocks, cf. Figure 1. The TS A has for each of its gadgets a $\gamma$-event in accordance to Table 1. Using these events, the joining connects the “initial states” of the gadgets as follows:

The $\gamma$-events $\gamma ^h_{i,j,\ell }$, where indices that are 0 are omitted, occur “lexicographically” ordered by $hij\ell$ in accordance to the canonical order on the natural numbers. This defines also an order on the gadgets and makes the conjunction unambiguous.

Due to space restrictions, most of the proof of Lemma 2. is omitted. However, the following lemma states the solvability of $\alpha$ and $v_1,\dots , v_n$ and exemplifies in which way A allows regions that respect the parameter.

Lemma 4

If (G, k) is a yes-instance of Regular Independent Set then the events $\alpha$ and $v_1,\dots , v_n$ are solvable by regions that respect the parameter $4rk+40$.

Proof

For the sake of space restrictions, we implicitly define solving regions $R_i=(sp_i, sg_i)$ by $sp_i(\iota )$ and $sg_i$, to be seen in Table 2: The $\iota$-column shows $sp(\iota )$. The event sets occur in the column in accordance to the signature of their elements. For example, $sp_1(e)=(b,0)$ for $e\in \{\alpha _1, \dots , \alpha _9\}$. Moreover, if $e\in E(A)$ does not occur in any presented set corresponding to $R_i$, then $sg_i(e)=(0,0)$. In particular, all signatures get along with (b, 0), (1, 0), (0, 0), (0, 1), (0, b). By $sp_i(s')=sp_i(s)-sg_i^-(e)+sp_i^+(e)$ for all , this defines $R_i$ completely.

Solving $\alpha$: Let $r\in \mathbb {N}^+$ such that every node of G has degree r, and let $I=\{v_{\ell _1},\dots , v_{\ell _k}\}$ be a k-independent set of G. The nodes $v_{\ell _1},\dots , v_{\ell _k}$ are independent, and each of it has exactly r adjacent edges. Thus, there are exactly rk edges $a_{i_1},\dots , a_{i_{rk}} \in E(G)$ such that for all $a\in E(G)$ the following is true. If $a\in E_I=\{a_{i_1},\dots , a_{i_{rk}}\}$, then $\vert a\cap I \vert =1$ and otherwise $\vert a\cap I \vert =0$. Using I and $E_I$, we define region $R_1$ in accordance to Table 2. If we follow the arguments for the proof of Lemma 2.1, then it is easy to see that $R_1$ is well defined and solves $\alpha$ at $x_{i,b+2}, x_{i,b+3}$ and $x_{i,2b+4}$ for all $i\in \{1,2,3\}$. Moreover, $\vert \,^{\!\bullet }R_1\vert \le k(r+1)+13$ and $\vert R_1^{\bullet }\vert \le k(r+1)+11$, cf. Table 2. Thus, the region $R_1$ respects the parameter. Notice that the latter is possible by grouping “similar” gadgets into blocks. For example, if the node noPros alternated with the node selectors ($P_1,T_1,\dots , P_n, T_n$), then the number of consuming and producing $\gamma$-events would depend on $\vert V(G)\vert$ and would not respect the parameter. The region $R_2$ of Table 2 solves $\alpha$ at the remaining states of A and respects the parameter.

Fig. 1.

The gadgets’ conjunction to finally build A, consisting of “blocks” in accordance to similar “gadget-types”. The red colored areas mark the gadgets whose initial states are mapped to b by $R_1$ (Table 2) solving $(\alpha , x_{i,b+2}), (\alpha , x_{i,b+3}), (\alpha , x_{i,2b+4})$ for all $i\in \{1,2,3\}$. (Color figure online)

Solving $v_i$, $i\in \{1,\dots , n\}$: The Region $R_3$ solves $v_i$ at all states except the sinks of the affected $\zeta$-events. The region $R_4$ solves $v_i$ at these remaining sinks. The event $v_i$ occurs in $G_{i_1},\dots , G_{i_r}$, $P_i$ and $U_i$. Thus, $\vert \,^{\!\bullet }R_3 \vert \le r+2$, $\vert \,^{\!\bullet }R_4\vert \le r$, $\vert R_3^{\bullet } \vert$ and $\vert R_4^{\bullet } \vert \le 1$.

Table 2. Implicitly defined regions of A that solve $\alpha$ and $v_i$ for all $i\in \{1,\dots , n\}$.

4 Conclusion

In this paper, we enhance our understanding of synthesizing (m, n)-T-systems from the viewpoint of parameterized complexity. Although (m, n)-Synthesis parameterized by $m+n$ belongs to XP, we show that there is little hope that this parameterization puts the problem into FPT. Future work might consider the occupancy number $o_N$ of a searched net N a parameter. Let $N=(P,T,f,M_0)$ be a pure b-net, and let RS be the set of N’s reachable markings. The occupancy number $o_p$ of a place $p\in P$ is defined by $o_p=\{M\in RS\mid M(p) >0\}$, and $o_N=max\{o_p\mid p\in P\}$ defines the occupancy number of N. At first glance, this parameter seems promising, at least synthesis parameterized by $o_N$ is in XP.