On the Parameterized Complexity of d-Restricted Boolean Net Synthesis

Abstract

In this paper, we investigate the parameterized complexity of d-restricted $\tau$-synthesis (dR$\tau$S) parameterized by d for a range of Boolean types of nets $\tau$. We show that dR$\tau$S is W[1]-hard for 64 of 128 possible Boolean types that allow places and transitions to be independent.

Supported by DFG through grant Be 1267/16-1 ASYST.

1 Introduction

Boolean Petri nets are one of the most well-known and used families of Petri nets, see  [2, pp. 139–152] (and references therein). For Boolean nets, a place p contains at most one token in every reachable marking. Thus, p is considered as a Boolean condition which is true if p is marked and false otherwise. In a Boolean Petri net, a place p and a transition t are related by one of the Boolean interactions: no operation ($\textsf {nop}$), input ($\textsf {inp}$), output ($\textsf {out}$), unconditionally set to true ($\textsf {set}$), unconditionally reset to false ($\textsf {res}$), inverting ($\textsf {swap}$), test if true ($\textsf {used}$), and test if false ($\textsf {free}$). These interactions define in which way p and t influence each other: The interaction $\textsf {inp}$ ($\textsf {out}$) defines that p must be true (false) before and false (true) after t’s firing; $\textsf {free}$ ($\textsf {used}$) implies that t’s firing proves that p is false (true); $\textsf {nop}$ means that p and t do not affect each other at all; $\textsf {res}$ ($\textsf {set}$) implies that p may initially be both false or true but after t’s firing it is false (true); $\textsf {swap}$ means that t inverts p’s current Boolean value.

A set $\tau$ of Boolean interactions is called a type of net. Since we have eight interactions to choose from, there are a total of 256 different types. A Boolean Petri net N is of type $\tau$ (a $\tau$-net) if it applies at most the interactions of $\tau$. For a type $\tau$, the $\tau$-synthesis problem consists in deciding whether a given directed labelled graph A, also called transition system, is isomorphic to the reachability graph of some $\tau$-net N, and in constructing N if it exists.

Badouel et al.  [1] and Schmitt  [4] investigated the computational complexity of $\tau$-synthesis for elementary net systems ($\{\textsf {nop},\textsf {inp},\textsf {out}\}$) and flip-flop nets ($\{\textsf {nop},\textsf {inp},\textsf {out},\textsf {swap}\}$), respectively; while synthesis is NP-complete for the former, it is polynomial for the latter. In [5], the complexity of $\tau$-synthesis restricted to g-bounded inputs (every state of A has at most g incoming and g outgoing arcs) has been completely characterized for the types that contain $\textsf {nop}$ and, thus, allow places and transitions to be independent. For 84 of these 128 types it turned out that synthesis is NP-complete, even for small fixed $g\le 3$. As a result, $\tau$-synthesis parameterized by g is certainly not fixed parameter tractable (FPT).

This paper addresses the computational complexity of a different instance of $\tau$-synthesis, namely d-restricted $\tau$-synthesis (dR$\tau$S), imposing a limitation for the synthesis output: The d-restricted synthesis targets to those $\tau$-nets in which every place must be in relation $\textsf {nop}$ with all but d transitions of the net, while the synthesis input is no longer confined. This formulation of the synthesis problem is motivated at least twofold. On the one hand, in applications, places are usually meant as resources while transitions are meant as agents. Hence such a restriction ensures that a certain resource binds only few agents. On the other hand, dR$\tau$S is of a particular interest from the theoretical point of view, since, parameterized by d, it belongs to the complexity class XP [5, p. 25]. Consequently, the question for the existence of FPT-algorithms arises.

In this paper, we enhance our understanding of dR$\tau$S from a parameterized complexity point of view and show W[1]-hardness for the following types of nets:

• 1. $\{\textsf {nop},\textsf {inp},\textsf {free}\}, \{\textsf {nop},\textsf {inp},\textsf {free}, \textsf {used}\},\{\textsf {nop},\textsf {out},\textsf {used}\},\{\textsf {nop},\textsf {out},\textsf {free},\textsf {used}\}$,

• 2. $\tau =\{\textsf {nop},\textsf {swap}\}\cup \omega$ such that $\omega \subseteq \{\textsf {inp},\textsf {out},\textsf {res},\textsf {set},\textsf {free},\textsf {used}\}$ and $\omega \cap \{\textsf {inp},\textsf {out},\textsf {free},\textsf {used}\}\not =\emptyset$

Our proofs base on parameterized reductions of the well-known W[1]-complete problems Regular Independent Set and Odd Set  [3]. While all types of (2) have been shown to be NP-complete [5], the types covered by (1) that does not contain any of $\textsf {res}, \textsf {set}$ have been shown to be polynomial [4, 6]. However, since our parameterized reductions are actually polynomial-time reductions, here we show NP-completeness and W[1]-hardness for these types at the same time.

The paper is organized as follows. After introducing of the necessary definitions in Sect. 2, the main contribution is presented in Sect. 3. Section 4 suggests an outlook of the further research directions.

2 Preliminaries

We assume that the reader is familiar with the concepts relating to fixed-parameter tractability. Due to space restrictions, some formal definitions and some proofs are omitted. See [3] for the definitions of relevant notions in parameterized complexity theory.

Transition Systems. A (deterministic) transition system (TS, for short) $A=(S,E, \delta )$ is a directed labeled graph with states S, events E and partial transition function $\delta : S\times E \longrightarrow S$, where $\delta (s,e)=s'$ is interpreted as . For we say s is a source and $s'$ is a sink of e, respectively. An event e occurs at a state s, denoted by , if $\delta (s,e)$ is defined. An initialized TS $A=(S,E,\delta , s_0)$ is a TS with a distinct state $s_0\in S$ where every state $s\in S$ is reachable from $s_0$ by a directed labeled path.

Boolean Types of Nets  [2]. The following notion of Boolean types of nets allows to capture all Boolean Petri nets in one uniform way. A Boolean type of net $\tau =(\{0,1\},E_\tau ,\delta _\tau )$ is a TS such that $E_\tau$ is a subset of the Boolean interactions: $E_\tau \subseteq I = \{\textsf {nop}, \textsf {inp}, \textsf {out}, \textsf {set}, \textsf {res}, \textsf {swap}, \textsf {used}, \textsf {free}\}$. The interactions $i \in I$ are binary partial functions $i: \{0,1\} \rightarrow \{0,1\}$ as defined in Fig. 1. For all $x\in \{0,1\}$ and all $i\in E_\tau$ the transition function of $\tau$ is defined by $\delta _\tau (x,i)=i(x)$. By definition, a Boolean type $\tau$ is completely determined by its event set $E_\tau$. Hence, in the following we identify $\tau$ with $E_\tau$, cf. Fig. 2.

Fig. 1.

All Interactions i of I. If a cell is empty, then i is undefined on the respective x.

Fig. 2.

Left: $\tau = \{ \textsf {nop}, \textsf {inp}, \textsf {free}\}$. Right: $\tilde{\tau } = \{ \textsf {nop}, \textsf {swap}, \textsf {used}, \textsf {set}\}$. The TS $A_1$ has no ESSP atoms. Hence, it has the $\tau$-ESSP and $\tilde{\tau }$-ESSP. The only SSP atom of $A_1$ is $(s_0, s_1)$. It is $\tilde{\tau }$-solvable by $R_1=(sup_1,sig_1)$ with $sup_1(s_0) = 0$, $sup_1(s_1) = 1$, $sig_1(a) = \textsf {swap}$. Thus, $A_1$ has the $\tau$-admissible set $\mathcal {R}=\{R_1\}$, and the $\tau$-net $N_A^{\mathcal {R}}= (\{ R_1\}, \{ a\}, M_0, f)$ with $M_0(R_1) = sup_1(R_1)$ and $f(R_1,a) = sig_1(R_1)$ solves $A_1$. The SSP atom $(s_0,s_1)$ is not $\tau$-solvable, thus, neither is $A_1$. TS $A_2$ has ESSP atoms $(b,r_1)$ and $(c,r_0)$, which are both $\tilde{\tau }$-unsolvable. The only SSP atom $(r_0,r_1)$ in $A_2$ can be solved by $\tilde{\tau }$-region $R_2=(sup_2, sig_2)$ with $sup_2(r_0) = 0$, $sup_2(r_1) = 1$, $sig_2(b) = \textsf {set}$, $sig_2(c) = \textsf {swap}$. Thus, $A_2$ has the $\tilde{\tau }$-SSP, but not the $\tilde{\tau }$-ESSP. None of the (E)SSP atoms of $A_2$ can be solved by any $\tau$-region. Notice that the $\tilde{\tau }$-region $R_2$ maps two events to a signature different from $\textsf {nop}$. Thus, in case of d-restricted $\tilde{\tau }$-synthesis, $R_2$ would be not valid for $d=1$.

$\tau$-Nets. Let $\tau \subseteq I$. A Boolean Petri net $N = (P, T, M_0, f)$ of type $\tau$, ($\tau$-net, for short) is given by finite and disjoint sets P of places and T of transitions, an initial marking $M_0: P\longrightarrow \{0,1\}$, and a (total) flow function $f: P \times T \rightarrow \tau$. For a natural number d, a $\tau$-net is called d-restricted if for every $p \in P :|\{ t \in T \mid f(p,t) \ne \textsf {nop}\} |\le d$. A $\tau$-net realizes a certain behavior by firing sequences of transitions: A transition $t \in T$ can fire in a marking $M: P\longrightarrow \{0,1\}$ if $\delta _\tau (M(p), f(p,t))$ is defined for all $p\in P$. By firing, t produces the next marking $M' : P\longrightarrow \{0,1\}$ where $M'(p)=\delta _\tau (M(p), f(p,t))$ for all $p\in P$. This is denoted by . Given a $\tau$-net $N=(P, T, M_0, f)$, its behavior is captured by a transition system $A_N$, called the reachability graph of N. The state set of $A_N$ is the reachability set RS(N), that is, the set of all markings that, starting from initial state $M_0$, are reachable by firing a sequence of transitions. For every reachable marking M and transition $t \in T$ with the state transition function $\delta$ of A is defined as $\delta (M,t) = M'$.

$\tau$-Regions. Let $\tau \subseteq I$. If an input A of $\tau$-synthesis allows a positive decision then we want to construct a corresponding $\tau$-net N purely from A. Since A and $A_N$ are isomorphic, N’s transitions correspond to A’s events. However, the notion of a place is unknown for TSs. So called regions mimic places of nets: A $\tau$-region of a given $A=(S, E, \delta , s_0)$ is a pair (sup, sig) of support $sup: S \rightarrow S_\tau = \{0,1\}$ and signature $sig: E\rightarrow E_\tau = \tau$ where every transition of A leads to a transition of $\tau$. A region (sup, sig) models a place p and the corresponding part of the flow function f. In particular, sig(e) models f(p, e) and sup(s) models M(p) in the marking $M\in RS(N)$ corresponding to $s\in S(A)$. We say that $\tau$-region (sup, sig) respects the parameter d, if $|\{e \in E \mid sig(e) \ne \textsf {nop}\} |\le d$. Every set $\mathcal {R}$ of $\tau$-regions of A defines the synthesized $\tau$-net $N^{\mathcal {R}}_A=(\mathcal {R}, E, f, M_0)$ with flow function $f((sup, sig),e)=sig(e)$ and initial marking $M_0((sup, sig))=sup(s_{0})$ for all $(sup, sig)\in \mathcal {R}, e\in E$. 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 [2]. A pair $(s, s')$ of distinct states of A defines a state separation atom (SSP atom, for short). A $\tau$-region $R=(sup, sig)$ solves $(s,s')$ if $sup(s)\not =sup(s')$. The meaning of 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 $\tau$-region that solves $(s,s')$ then s and $s'$ are called $\tau$-solvable. If every SSP atom of A is $\tau$-solvable then A has the $\tau$-state separation property ($\tau$-SSP, for short). A pair (e, s) of event $e\in E$ and state $s\in S$ where e does not occur at s, that is , defines an event state separation atom (ESSP atom, for short). A $\tau$-region $R=(sup, sig)$ solves (e, s) if sig(e) is not defined on sup(s) in $\tau$, that is, $\lnot \delta _\tau (sup(s), sig(e))$. 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 $\tau$-region that solves (e, s) then e and s are called $\tau$-solvable. If every ESSP atom of A is $\tau$-solvable then A has the $\tau$-event state separation property ($\tau$-ESSP, for short). A set $\mathcal {R}$ of $\tau$-regions of A is called $\tau$-admissible if for every of A’s (E)SSP atoms there is a $\tau$-region R in $\mathcal {R}$ that solves it. The following lemma, borrowed from [2, p.163], summarizes the already implied connection between the existence of $\tau$-admissible sets of A and (the solvability of) $\tau$-synthesis:

Lemma 1

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

In this paper, we investigate the following parameterized problem: d-Restricted $\tau$-Rynthesis (dR$\tau$S). The input (A, d) consists of a TS A and a natural number $d\in \mathbb {N}$. The parameter is d. The question to answer is, if there is a $\tau$-admissible set $\mathcal {R}$ of A such that $\vert \{e\in E(A)\mid sig(e)\not =\textsf {nop}\}\vert \le d$ is true for all $R\in \mathcal {R}$.

3 W[1]-Hardness of d-Restricted $\tau$-Synthesis

Theorem 1

The problem d-restricted $\tau$-synthesis is W[1]-hard if

• 1. $\tau =\{\textsf {nop},\textsf {inp},\textsf {free}\}$ or $\tau =\{\textsf {nop},\textsf {inp},\textsf {free}, \textsf {used}\}$ or $\tau =\{\textsf {nop},\textsf {out},\textsf {used}\}$ or $\tau =\{\textsf {nop},\textsf {out},\textsf {free},\textsf {used}\}$,

• 2. $\tau =\{\textsf {nop},\textsf {swap}\}\cup \omega$ such that $\omega \subseteq \{\textsf {inp},\textsf {out},\textsf {res},\textsf {set},\textsf {free},\textsf {used}\}$ and $\omega \cap \{\textsf {inp},\textsf {out},\textsf {free},\textsf {used}\}\not =\emptyset$

The proofs of Theorem 1.1 and Theorem 1.2 base on parameterized reductions of the problems Regular Independent Set and Odd Set, respectively. Both problems are well-known to be W[1]-complete (see e.g. [3]) and are defined as follows:

Regular Independent Set (RIS). The input $(\mathfrak {U}, M,\kappa )$ consists of a finite set $\mathfrak {U}$, a set $M=\{M_0,\dots , M_{m-1}\}$, $M_i\subseteq \mathfrak {U}$ and $\vert M_i\vert =2$ for all $i\in \{0,\dots , m-1\}$, and $\kappa \in \mathbb {N}$. The parameter is $\kappa$. Moreover, there is $r\in \mathbb {N}$ for all $X\in \mathfrak {U}$ such that $\vert \{ a \in M \mid X\in a\}\vert =r$. The question is whether there is an independent set $S\subseteq \mathfrak {U}$, that is, $\{X,X'\}\not \in M$ for all $X,X'\in S$, such that $\vert S\vert \ge \kappa$.

Odd Set (OD). The input $(\mathfrak {U},M, \kappa )$ consists of a finite set $\mathfrak {U}$, a set $M=\{M_0,\dots , M_{m-1}\}$ of subsets of $\mathfrak {U}$ and a natural number $\kappa$. The parameter is $\kappa$. The question to answer is whether there is a set $S\subseteq \mathfrak {U}$ of size at most $\kappa$ such that $\vert S\cap M_i\vert$ is odd for every $i\in \{0,\dots , m-1\}$.

The General Reduction Idea. An input $I=(\mathfrak {U}, M, \kappa )$ (of RIS or OD), where $M=\{M_0,\dots , M_{m-1}\}$, is reduced to an instance $(A^\tau _I, d)$ with TS $A^\tau _I$ and $d=f(\kappa )$ (f being a polynomial time computable function) as follows: For every $i\in \{0,\dots , m-1\}$, the TS $A^\tau _I$ has for the set $M_i=\{X_{i_0},\dots , X_{i_{m_i-1}}\}$ a directed labelled path that represents $M_i$ and uses its elements as events. The TS $A^\tau _I$ has an ESSP atom $\alpha$ such that if $R=(sup, sig)$ is a $\tau$-region that solves $\alpha$ and respects d, then there are indices $i_0,\dots , i_j\in \{0,\dots , m-1\}$ such that $sup(s_{i_\ell ,0})\not =sup(s_{i_\ell ,m_{i_\ell }})$ for all $\ell \in \{0,\dots , j\}$. Since the image of $P_{i_\ell }$ is a directed path in $\tau$, by $sup(s_{i_\ell ,0})\not =sup(s_{i_\ell ,m_{i_\ell }})$, there has to be an element $X\in M_{i_\ell }$ such that implies $sup(s)\not =sup(s')$. That is, X causes a state change in $\tau$. This is simultaneously true for all $P_{i_0},\dots , P_{i_j}$. The reduction ensures that defines a searched independent set or a searched odd set, depending on the actually reduced problem. Thus, if $(A^\tau _I, d)$ is a yes-instance, implying the solvability of $\alpha$, then $I=(\mathfrak {U}, M, \kappa )$ is, too.

Reversely, if $I=(\mathfrak {U}, M, \kappa )$ is a yes-instance, then there is a fitting $\tau$-region of $A^\tau _I$ that solves $\alpha$. The reduction ensures that the $\tau$-solvability of $\alpha$ implies that all (E)SSP atoms of $A^\tau _I$ are solvable by $\tau$-regions respecting d. Thus, $(A^\tau _I,d)$ is a yes-instance, too.

In what follows, we present the corresponding reductions, show that the solvability of $\alpha$ implies a searched (independent or odd) set and argue that the existence of a searched set implies the solvability of $\alpha$.

The Proof of Theorem 1.1. Let $\tau \in \{\{\textsf {nop},\textsf {inp},\textsf {free}\}, \{\textsf {nop},\textsf {inp},\textsf {free}, \textsf {used}\}\}$. We prove the claim for $\tau$, by symmetry, the proof for the other types is similar.

Let $I=(\mathfrak {U}, M, \kappa )$ be an instance of RIS, where $M=\{M_0,\dots , M_{m-1}\}$ such that $M_i=\{X_{i_0}, X_{i_1}\}$ and (without loss of generality we assume that) $i_0 < i_1$ for all $i\in \{0,\dots , m-1\}$. Let $r\in \mathbb {N}$ such that $\vert \{ a \in M \mid X\in a\}\vert =r$ for all $X\in \mathfrak {U}$.

For a start, we define $d=\kappa \cdot (r+1)+2$. The TS $A^\tau _I$ has the following gadget H with events $k_0$ and $k_1$ that provides the atom $\alpha =(k_1,h_0)$:

Moreover, for every $i\in \{0,\dots , m-1\}$, the TS $A^\tau _I$ has the following gadget $T_i$ that represents $M_i=\{X_{i_0}, X_{i_1}\}$:

The gadget $T_i$ uses $M_i$’s elements $X_{i_0}$ and $X_{i_1}$ as events. Moreover, it has exactly $r\kappa$ events $a^0_i,\dots , a^{r\kappa -1}_i$ that occur consecutively on a path. If $i\in \{0,\dots , m-1\}$ and $j\in \{0,\dots , r\kappa -1\}$, then we say $a_i^j$ is the j-th event of (the set) $M_i$. For every $j\in \{0,\dots , r\kappa -1\}$, the TS $A^\tau _I$ has the following gadget $G_j$:

For all $i\in \{0,\dots , m-1\}$, the gadget $G_i$ applies the j-th event of $M_i$, and the events $a_0^j,\dots , a_{m-1}^j$ occur consecutively in a row.

The initial state of $A^\tau _I$ is $\bot _{m-1,0}$. Fresh events $\ominus _{0},\dots , \ominus _{m-1}$ and $\odot _0,\dots , \odot _{r\kappa -1}$ join the introduced gadgets H, $T_0,\dots , T_{m-1}$ and $G_0,\dots ,G_{r\kappa -1}$ into the TS $A^\tau _I$ and make all states reachable from $\bot _{m-1,0}$. More exactly, for all $i\in \{1,\dots , m-1 \}$, the TS $A^\tau _I$ has the edge , and it has the edge . Moreover, $A^\tau _I$ has the edge and, for all $j\in \{0,\dots , r\kappa -2 \}$, the edge . The resulting TS is $A^\tau _I$, and it is easy to see that $(A^\tau _I, d)$ is obtained by a parameterized reduction.

Let $(A^\tau _I, d)$ be a yes-instance. We argue that $(\mathfrak {U}, M,\kappa )$ has an independence set of size $\kappa$. Since $(A^\tau _I, d)$ is a yes-instance, there is a $\tau$-region $R=(sup, sig)$ that solves $\alpha$ and respects the parameter d, that is, $\vert \{e\in E(A^\tau _I) \mid sig(e)\not =\textsf {nop}\}\vert \le d$. In the following, we argue that $S=\{X\in \mathfrak {U} \mid sig(X)=\textsf {inp}\}$ is a searched set. The general idea is as follows: The region R selects exactly $r\kappa$ gadgets $T_{i_0}, \dots T_{i_{r\kappa -1}}$, representing the sets $M_{i_0},\dots , M_{i_{r\kappa -1}}$, such that $sup(t_{i_j, 0})=1$ and $sup(t_{i_j, 2})=0$ for all $j\in \{0,\dots , r\kappa -1\}$. In particular, for all $j\in \{0,\dots , r\kappa -1\}$, that makes a path from 1 to 0 in $\tau$. Consequently, for every $j\in \{0,\dots , r\kappa -1\}$, there is exactly one event $e\in \{X_{{i_j}_0}, X_{{i_j}_1}\}$ with $sig(e)=\textsf {inp}$. The reduction ensures that there are exactly $\kappa$ elements $X_{i_0}, \dots , X_{i_{\kappa -1}}\in \mathfrak {U}$ such that $sig(X_{i_j})=\textsf {inp}$ for all $j\in \{0,\dots , \kappa -1\}$. Moreover, it also ensures $sig(e)=\textsf {nop}$ for all $e\in \mathfrak {U}\setminus \{X\in \mathfrak {U}\mid sig(X)=\textsf {inp}\}$. As a result, $r\kappa$ sets are “covered” by $\kappa$ elements. Since every elements is a member of exactly r sets, $S=\{X\in \mathfrak {U}\mid sig(X)=\textsf {inp}\}$ is an independent set of size $\kappa$ of $(\mathfrak {U}, M)$.

Let us formally argue that the reduction correctly converts this general idea. By definition of $\tau$, one easily finds out that $sig(k_1)=\textsf {free}$, $sup(h_{0})=1$ and $sig(k_0)=\textsf {inp}$. By , this implies $sup(t_{i,0})=1$ for all $i\in \{0,\dots , m-1\}$. Moreover, since R respects d, there are at most $\kappa \cdot (r+1)$ other events left whose signature is different from $\textsf {nop}$.

Let $j,j'\in \{0,\dots , r\kappa -1\}$ such that $j\not =j'$. By $sig(k_0)=\textsf {inp}$ and , we have $sup(g_{j,0})=1$; by $sig(k_1)=\textsf {free}$ and , we have $sup(g_{j,m})=0$. Consequently, is a path from 1 to 0 in $\tau$. Since there is no path in $\tau$ on which $\textsf {inp}$ occurs twice, there is exactly one $i\in \{0,\dots , m-1\}$ such that $sig(a_i^j)=\textsf {inp}$. Similarly, there is exactly one $i'\in \{0,\dots , m-1\}$ such that $sig(a_{i'}^{j'})=\textsf {inp}$. For all $i\in \{0,\dots , m-1\}$, the events $a_i^0,\dots , a_i^{r\kappa -1}$ occur consecutively on a path in $T_i$, and $\textsf {inp}$ never occurs twice on a path in $\tau$. Thus, by $j\not =j'$, we have $i\not =i'$, that is, never the j-th and the $j'$-th event of the same set $M_i$ are selected. Consequently, by the arbitrariness of j and $j'$, there are exactly $r\kappa$ events $a_{i_0}^{j_0}, \dots , a_{i_{r\kappa -1}}^{j_{r\kappa -1}}$ such that $sig(a_{i_0}^{j_0})=\dots =sig(a_{i_{r\kappa -1}}^{j_{r\kappa -1}})=\textsf {inp}$, and all $i_0,\dots , i_{r\kappa -1}\in \{0,\dots , m-1\}$ are pairwise distinct. On the one hand, this shows that there are $r\kappa$ gadgets $T_{i_0}, \dots , T_{i_{r\kappa -1}}$ (representing the sets $M_{i_0},\dots , M_{i_{r\kappa -1}}$) such that $sup(t_{i_j,0})=1$ and $sup(t_{i_j, 2})=0$ for all $j\in \{0,\dots , r\kappa -1\}$. Thus, for every $j\in \{0,\dots , r \kappa -1\}$ there is an event $X \in \{X_{{i_j}_{0}}, X_{ {i_j}_{1} }\}$ with $sig(X)=\textsf {inp}$. On the other hand, since R respects d and $\vert \{ k_0,k_1, a_{i_0}^{j_0}, \dots , a_{i_{r\kappa -1}}^{j_{r\kappa -1}} \}\vert =r\kappa +2$, there are at most $\kappa$ events $X_{i_0},\dots , X_{i_{\kappa -1}}\in \mathfrak {U}$ whose signature is different from $\textsf {nop}$. Thus, $r\kappa$ sets are “covered” by at most $\kappa$ elements. Since every element is a member of exactly r sets, this is only possible if defines an independent set of size $\kappa$.

Let $(\mathfrak {U}, M, \kappa )$ be a yes-instance of RIS. In the following we argue that $\alpha$ is solvable by a $\tau$-region that respects the parameter. Let S be an independent set of size $\kappa$. Every element of $\mathfrak {U}$ occurs in exactly r sets. Thus, there are exactly $r\kappa$ sets $M_{i_0},\dots , M_{i_{r\kappa -1}}\in M$ such that $S\cap M_{i_j}\not =\emptyset$ for all $j\in \{0,\dots , r\kappa -1\}$. We define $R=(sup, sig)$ as follows: $sup(\bot _{m-1,0})=1$; for all $e\in E(A^\tau _I)$, if $e\in \{k_0\}\cup S$, then $sig(e)=\textsf {inp}$; if $e=k_1$, then $sig(k_1)=\textsf {free}$; if $e=a_{i_j}^j$ and $j\in \{0,\dots , r\kappa -1\}$, then $sig(a_{i_j}^j)=\textsf {inp}$; else $sig(e)=\textsf {nop}$.

For all $s\in S(A^\tau _I)\setminus \{\bot _{m-1,0}\}$, there is a path . By inductive defining $sup(s_{i+1})=\delta _\tau (s_i,sig(e_{i+1}))$ for all $i\in \{0,\dots , n-1\}$, we obtain sup. One easily verifies that (sup, sig) is a fitting region that solves $\alpha$.    $\square$

The Proof of Theorem 1.2 for . Let $I=(\mathfrak {U}, M, \kappa )$ be an instance of OD, that is, $\mathfrak {U}=\{X_0,\dots , X_{n-1}\}$, $M=\{M_0,\dots , M_{m-1}\}$ and $M_i=\{X_{i_0},\dots , X_{i_{m_i-1}}\}\subseteq \mathfrak {U}$ for all $i\in \{0,\dots , m-1\}$. Without loss of generality, we assume $i_0< i_1< \dots< i_{m_i-2} < i_{m_i-1}$ for all $i\in \{0,\dots , m-1\}$.

For a start, we define $d=2\kappa +2$. The TS $A^\tau _I$ has the following gadget H that applies the events k, z, o and $w_m$ and provides the atom $\alpha =(k,h_2)$:

Next, we introduce $A^\tau _I$’s gadgets using the elements of $\mathfrak {U}=\{X_0,\dots , X_{n-1}\}$ as events. Moreover, these gadgets use also the events of $\mathfrak {u}=\{x_0,\dots , x_{n-1}\}$, and $\mathfrak {U}$ and $\mathfrak {u}$ are connected as follows: For every $i\in \{0,\dots , n-1\}$, the event $X_i$ is associated with the event $x_i$ such that is an edge in $A^\tau _I$ if and only if is an edge in $A^\tau _I$. In particular, for all $i\in \{0,\dots , m-1\}$, the TS $A^\tau _I$ has for the set $M_i=\{X_{i_0},\dots , X_{i_{m_i-1}}\}$ the following gadget $T_i$ that uses the elements of $M_i$ (and their associated events of $\mathfrak {u}$) as events:

We postpone the actual joining of $H, T_0,\dots , T_{m-1}$ and argue first that a d-restricted $\tau$-region $R=(sup, sig)$ solving $\alpha$ implies a searched odd set S.

Since R solves $\alpha$ and $\tau \cap \{\textsf {free},\textsf {used}\}=\emptyset$, we have $sig(k)\in \{\textsf {inp},\textsf {out}\}$. In what follows, we assume $sig(k)=\textsf {inp}$ and argue that defines a fitting odd set of size at most $\kappa$. By symmetry, the case $sig(k)=\textsf {out}$ is similar.

Since R solves $\alpha$ and $sig(k)=\textsf {inp}$, we have $sup(h_2)=0$. Moreover, for all $s\in S(A^\tau _I)$, if , then $sup(s)=0$, and if , then $sup(s)=1$. By and , this implies $sig(z)=\textsf {nop}$; by , this implies $sig(o)\not =\textsf {nop}$. Let $i\in \{0,\dots , m-1\}$ be arbitrary but fixed. By $sig(z)=\textsf {nop}$ and and we obtain $sup(t_{i,1})=0$ and $sup(t_{i,m_i+1})=1$. Thus, the path is a path from 0 to 1 in $\tau$. In particular, the number of state changes between 0 and 1 on this path is odd. Consequently, since every $X\in M_i$ occurs once in $T_i$, the number is odd. Since i was arbitrary, this is simultaneously true for all gadgets $T_0,\dots , T_{m-1}$. In the following, we show that $\vert S\cap M_i\vert$ is odd for all $i\in \{0,\dots , m-1\}$. To do so, we argue that for all $X\in S$ and $T_i\not =T_j$, $i,j\in \{0,\dots , m-1\}$, with and the following is true: If $sup(s)\not =sup(s')$, then $sup(q)\not =sup(q')$. Intuitively, there is no X contributing to a state change in $T_i$ but not in $T_j$. Since X always occurs with its associated event x, both and are present. Thus, if $sup(s)=0$ and $sup(s')=1$, then $sig(X)\in \{\textsf {out}, \textsf {set}, \textsf {swap}\}$ and $sig(x)\in \{\textsf {inp},\textsf {res},\textsf {swap}\}$. Clearly, if $sig(X)=\textsf {swap}$ or $sig(x)=\textsf {swap}$, then $sup(q)\not =sup(q')$. Otherwise, if $sig(X)\in \{\textsf {out}, \textsf {set}\}$ and $sig(x)\in \{\textsf {inp},\textsf {res}\}$, then and imply $sup(q)=0\not =sup(q')=1$. Similarly, if $sup(s)=1$ and $sig(s')=0$, then also $sup(q)\not =sup(q')$. Consequently, $\vert S\cap M_i\vert$ is odd for all $i\in \{0,\dots , m-1\}$.

We argue that $\vert S\vert \le \kappa$. Every $X\in S$ occurs always with its associated event $x\in \mathfrak {u}$: if , then . Moreover, $X\in S$ implies $sup(s)\not =sup(s')$ and, thus, $sig(X)\not =\textsf {nop}$ and $sig(x)\not =\textsf {nop}$. Recall that $sig(k), sig(o)\not \in \{\textsf {nop}\}$. Consequently, if $\vert S\vert \ge \kappa +1$, then $\vert \{e\in E(A^\tau _I)\mid sig(e)\not =\textsf {nop}\}\vert \ge 2\kappa +4$, a contradiction. This proves $\vert S\vert \le \kappa$. In particular, S defines a searched odd set.

In the following, we complete the construction of $A^\tau _I$. In order to do that, for all $i\in \{0,\dots , m-1\}$, we enhance $T_i$ to a (path) gadget with starting state $\top _i$. This extension of $T_i$ is necessary to ensure that if $\alpha$ is solvable by a $\tau$-region that respects d, then all of $A^\tau _I$’s (E)SSP atoms are too. To finally obtain $A^\tau _I$, we use fresh events $\ominus _1,\dots , \ominus _m$ and thread $G_0,\dots , G_{m-1}$ and H on a chain, that is, .

Let $j\in \{0,\dots , m-1\}$ and $\ell \in \{0,\dots , m_j\}$. We define the set $V_{j,\ell }$ as follows:

$$V_{j,\ell }= {\left\{ \begin{array}{ll} \{X_{j_0}\}, &{} \text {if } \ell =0\\ \{X_{j_{\ell -1}}, X_{j_\ell }\}, &{} \text {if } 1\le \ell \le m_j-1\\ \{X_{j_{m_j-1}}\}, &{} \text {if } \ell =m_j\\ \end{array}\right. } $$

Let $i\in \{0,\dots , m-1\}$ and $j\in \{0,\dots , i-1,i+1,\dots , m-1\}$. The number $\sigma _{i,j}$ of elements of $V_j=\{V_{j,0},\dots , V_{j,m_j}\}$ that are subsets of $M_i$ is defined by $\sigma _{i,j}=\vert \{V\in V_j\mid V\subseteq M_i \}\vert$. Let $\ell _0,\dots , \ell _{\sigma _{i,j}-1}\in \{0,\dots , m_j-1\}$ be the pairwise distinct indices (in increasing order) such that $V_{j, \ell _k}\subseteq M_i$ for all $k\in \{0,\dots , \sigma _{i,j}-1\}$. The gadget $G_i$ implements events $u_{\ell _0}^{i,j},v_{\ell _0}^j,\dots ,u_{\ell _{\sigma _{i,j}-1}}^{j,i}, v_{\ell _{\sigma _{i,j}-1}}^j$ consecutively on the following path $P_i^j=$

Notice that the events $v_{\ell _0}^j,\dots , v_{\ell _{\sigma _{i,j}-1}}^j$ might occur on different paths of $A^\tau _I$, that is, $P_i^j$ and $P_{i'}^j$ where $i\not =i'$. On the other hand, the events $u_{\ell _0}^{j,i}, \dots , u_{\ell _{\sigma _{i,j}-1}}^{j,i}$ occur exactly once in $A^\tau _I$ (on the path $P_i^j$). The gadget $G_i$ is finally built as follows. If $\sigma _{i,j}=0$ for all $j\in \{0,\dots ,i-1,i+1,\dots , m-1\}$, then . That is, we extend $T_i$ simply by the edge . Otherwise, $G_i$ is given by

where $j_0,\dots , j_\ell \in \{0,\dots , i-1,i+1,\dots , m-1\}$, $j_0<\dots < j_\ell$, are exactly the indices such that $\sigma _{i,j_k} > 0$ for all $k\in \{0,\dots , \ell \}$. This finally results in $A^\tau _I$, and it is easy to see that this is a parameterized (and even polynomial) reduction.

Fig. 3.

The TS $A^\tau _{I_0}$ that origins from $I_0$, defined by Example 1. Top: $P_0^1$ (red), $P_0^2$ (olive), $P_0^3$ (blue). The red colored circles sketch the states mapped to 1 by the region R that bases on $S_0$, solves $(k, h_2)$ and respects $d=5$. (Color figure online)

Example 1

Let $I_0=(\mathfrak {U}, M, \kappa )$ be (the yes-instance) defined by $\mathfrak {U}=\{X_0,\dots , X_4\}$, $M= \{M_0,\dots , M_3\}$ with $M_0=\{X_0,X_1,X_2\}$, $M_1=\{X_0,X_3\}$, $M_2=\{X_1,X_2\}$ and $M_3=\{X_2,X_3,X_4\}$ and $\kappa =3$. The set $S_0=\{X_2,X_3,X_4\}$ is a fitting odd set of size 3. By definition, $V_{0,0}=\{X_0\}$, $V_{0,1}=\{X_0,X_1\}$, $V_{0,2}=\{X_1, X_2\}$ and $V_{0,3}=\{X_2\}$; $V_{1,0}=\{X_0\}$, $V_{1,1}=\{X_0,X_3\}$ and $V_{1,2}=\{X_3\}$; $V_{2,0}=\{X_1\}$, $V_{2,1}=\{X_1,X_2\}$ and $V_{2,2}=\{X_2\}$; $V_{3,0}=\{X_2\}$, $V_{3,1}=\{X_2,X_3\}$, $V_{3,2}=\{X_3, X_4\}$ and $V_{3,3}=\{X_4\}$.

For $G_0$, we have $V_{1,0}\subseteq M_0$, $V_{1,1}\not \subseteq M_0$ and $V_{1,2}\not \subseteq M_0$. Thus, $\sigma _{0,1}=1$. By $V_{2,0}\subseteq M_0$, $V_{2,1}\subseteq M_0$ and $V_{2,2}\subseteq M_0$, we have $\sigma _{0,2}=3$. Finally, only $V_{3,0}$ is a subset of (interest of) $M_0$, thus, $\sigma _{0,3}=1$. The red, olive and blue colored paths of Fig. 3 show $P_{0,1}, P_{0,2}$ and $P_{0,3}$, respectively.

For $G_1$, the only set of interest is $V_{0,0}\subseteq M_1$, thus $\sigma _{1,0}=0$ and $\sigma _{1,2}=\sigma _{1,3}=0$. For $G_2$, we have $V_{0,2}, V_{0,3}, V_{3,0}\subseteq M_2$, thus, $\sigma _{2,0}=2$, $\sigma _{2,1}=0$ and $\sigma _{2,3}=1$. For $G_3$, we observe $V_{0,3}, V_{1,2}, V_{2,2}\subseteq M_3$, thus, $\sigma _{3,0}=\sigma _{3,1}=\sigma _{3,2}=1$. Figure 3 finally shows the joining of $G_0, \dots , G_3$ and H into $A^\tau _{I_0}$.

So far, we have argued that if $(A^\tau _I,d)$ is a yes-instance, then $(\mathfrak {U}, M,\kappa )$ is too. In the following, we argue that if S is a fitting odd set S of $(\mathfrak {U}, M,\kappa )$, then $\alpha$ is solvable by a $\tau$-region $R=(sup, sig)$ that respects d: $sup(\top _0)=1$; for all $e\in E(A^\tau _I)$, if $e=k$, then $sig(k)=\textsf {inp}$; if $e\in \{o\} \cup S\cup \{x\in \mathfrak {u}\mid X\in S\}$, then $sig(e)=\textsf {swap}$; otherwise, $sig(e)=\textsf {nop}$. By $A^\tau _I$’s reachability, one easily finds that this properly defines R. Figure 3 sketches R for the odd set $S=\{X_2,X_3,X_4\}$.    $\square$

If $\tau$ is a type of Theorem 1.2 such that $\tau \cap \{\textsf {used},\textsf {free}\}\not =\emptyset$, then the former reduction generally does not fit. For example, if $\tau =\{\textsf {nop}, \textsf {swap},\textsf {used}\}$, then a $\tau$-solvable TS A satisfies that implies . Since $\textsf {used}$ is the only interaction of $\tau$ that ever allows $\tau$-solvability of ESSP atoms, $(e,s')$ would be unsolvable otherwise. Thus, for $\tau =\{\textsf {nop}, \textsf {swap},\textsf {used}\}$, the previous reduction yields always no-instances. However, if $\tau$ is a type of Theorem 1.2 such that $\tau \cap \{\textsf {used},\textsf {free}\}$, then the reduction of the following proof fits for $\tau$.

The Proof of Theorem 1.2 for . For a start, we define $d=\kappa +4$. The TS $A^\tau _I$ has the following gadgets $H_0, H_1$ with events $k,z_0,z_1,o_0$ and $o_1$ that provide the atom $\alpha =(k,h_{0,2})$:

Moreover, for every set $M_i=\{X_{i_0},\dots , X_{m_i-1}\}$, $i\in \{0,\dots , m-1\}$, the TS $A^\tau _I$ has the following gadget $T_i$ that uses the elements of $M_i$ as events:

Moreover, we extend $T_i$ to a gadget in exactly the same way like the previous reduction for $\tau \cap \{\textsf {used},\textsf {free}\}=\emptyset$. Finally, for all $i\in \{0,\dots , m-1\}$, we use the fresh events $\ominus _1,\dots , \ominus _{m+1}$ and apply the edges .

Let $R=(sup, sig)$ be a $\tau$-region that solves $\alpha$ and respects d. Let $e\in E(A^\tau _I)$ be arbitrary. Since implies , $sig(e)\not \in \{\textsf {inp},\textsf {out}\}$ is true. In particular, since R solves $\alpha$, $sig(k)\in \{\textsf {used}, \textsf {free}\}$. Moreover, if $sup(s)\not =sup(s')$, then $sig(e)=\textsf {swap}$.

In what follows, we assume $sig(k)=\textsf {used}$, which implies $sup(h_{0,0})=0$ and, thus, $sig(o_0)=sig(o_1)=\textsf {swap}$. By symmetry, the case $sig(k)=\textsf {free}$ is similar. By $sig(k)=\textsf {used}$, is a path from 1 to 1 in $\tau$. In particular, the number $\vert \{e\in \{z_0,z_1,o_0\} \mid sig(e)=\textsf {swap}\}\vert$ is even. Since $sig(o_0)=\textsf {swap}$, there is exactly one event $e\in \{z_0,z_1\}$ such that $sig(e)=\textsf {swap}$. In the following, we assume $sig(z_0)=\textsf {swap}$ implying $sig(z_1)\in \{\textsf {nop},\textsf {used}\}$. By symmetry, the case $sig(z_1)=\textsf {swap}$ is similar. Since R respects d, there are at most $\kappa$ events left whose signature is different from $\textsf {nop}$. Let $i\in \{0,\dots , m-1\}$ be arbitrary but fixed. By $sig(k)=\textsf {inp}$, $sig(z_0)=\textsf {swap}$ and $sig(z_1)\in \{\textsf {nop},\textsf {used}\}$, the path is a path from 0 to 1 in $\tau$. Similar to the case $\tau \cap \{\textsf {used}, \textsf {free}\}=\emptyset$, the set of elements of $\mathfrak {U}$ mapped to $\textsf {swap}$ implies a searched odd set of M.

For the reverse direction, let $S\subseteq \mathfrak {U}$ be an odd size of size at most $\kappa$ of M. We obtain a $\tau$-region $R=(sup, sig)$ that solves $(k, h_{0,2})$ an respects d as follows: For a start, we let $sup(\top _0)=1$. Moreover, for all $e\in E(A^\tau _I)$, if $e=k$, then $sig(e)=\textsf {used}$; if $e\in \{o_0,o_1,z_0\}\cup S$, then $sig(e)=\textsf {swap}$; otherwise $sig(e)=\textsf {nop}$. This implicitly defines a fitting region that solves $\alpha$.    $\square$

4 Conclusion

In this paper, we investigate the parameterized complexity of dR$\tau$S parameterized by d and show W[1]-completeness for a range of Boolean types. As a result, d is ruled out for fpt-approaches for the considered types of nets. As future work, one may investigate the parameterized complexity of dR$\tau$S for other boolean types [5]. Moreover, one may look for other more promising parameters: If $N=(P, T, M_0, f)$ is a Boolean net, $p\in P$ and if the occupation number $o_p$ of p is defined by $o_p=\vert \{ M\in RS(N) \mid M(p)=1\} \vert$ then the occupation number $o_N$ of N is defined by $o_N=\text {max}\{ o_p \mid p\in P\}$. If $\mathcal {R}$ is a $\tau$-admissible set (of a TS A) and $R\in \mathcal {R}$, then the support of R determines the number of markings of $N_A^{\mathcal {R}}$ that occupy R, that, is, $o_R=\vert \{s \in S(A) \mid sup(s)=1 \}\vert$. Thus, searching for a $\tau$-net where $o_N\le n$, $n\in \mathbb {N}$, corresponds to searching for a $\tau$-admissible set $\mathcal {R}$ such that $\vert \{s \in S(A) \mid sup(s)=1\} \vert \le n$ for all $R\in \mathcal {R}$. As a result, for each (E)SSP atom $\alpha$ there are at most $\mathcal {O}(\left( {\begin{array}{c}\vert S\vert \\ o_N\end{array}}\right) )$ fitting supports for $\tau$-regions solving $\alpha$. Thus, the corresponding problem $o_N$-restricted $\tau$-synthesis parameterized by $o_N$ is in XP if, in a certain sense, $\tau$-regions are fully determined by a given support sup.