# Theory of Regions for Control Synthesis without Computing Reachability Graph
## 2 Background  
A Petri net is a directed graph consisting of places, transitions and valued arcs connecting them. Formally, a PN is a bipartite graph \(N=(T,P,Pre,Post)\). \(P\) is a finite set of places. \(T\) is a finite set of transitions [1]. \(Pre:P\times T\rightarrow\mathbb{N}\) is the pre-incidence function that specify weighted arcs from \(P\) to \(T\). \(\mathbb{N}\) is the set of nonnegative integers. In addition, \(Post:P\times T\rightarrow\mathbb{N}\) is the post-incidence function that specify weighted arcs from \(T\) to \(P\). The transitions of a PN can be partitioned into two disjoint subsets: \(T_{u}\) the set of uncontrollable transitions and \(T_{c}\) the set of controllable transitions. Controllable transitions can be disabled by the PN controller, while uncontrollable transitions cannot. Let \(p^{(t)}\) (respectively, \({}^{(t)}p\)) be the set of output transitions (respectively, input transitions) of the place \(p\). A PN can be represented by the so-called incidence matrix \(C\) defined as \(C(p,t)=Post(p,t)-Pre(p,t)\). Let \(t^{(p)}\) (respectively, \({}^{(p)}t\)) the set of output places (respectively, input places) of transition t. Besides, let \(\mathbb{G}(N,M_{0})\) be the reachability graph constructed from the initial marking \(M_{0}\) of a given PN. M represents the set of markings \(M\in G(N,M_{0})\). A transition \(t\in T\) is enabled from a marking \(M\) (denoted by \(M[t>)\) if and only if \(\mathbb{M}\geq\mathrm{Pre}(.,t)\) if an enabled transition t is fired, it leads to a new marking \(M^{\prime}\) such that: \(M^{\prime}=M+C(.,t)\). This can be denoted by \(M[t>M^{\prime}\). A marking \(M^{\prime}\) is accessible from a given marking \(M\) if there exists a firing sequence \(\sigma=t_{1},t_{2}\ldots t_{n}\) transforming \(M\) into \(M^{\prime}\). By firing a sequence \(\sigma\) any marking \(M\) reachable from \(M_{0}\) satisfies the following state equation of Petri nets:  
\[M=M_{0}+C\overrightarrow{\sigma} \tag{1}\]  
\(\overrightarrow{\sigma}:T\rightarrow\mathbb{N}\) is a vector of nonnegative integers is the occurrence of transition t in \(\sigma\). Let \(C\) be the incidence matrix of marked PN. \(C\big{(}p_{i},t_{j}\big{)}=w\big{(}t_{j},p_{i}\big{)}\) if, \(C\big{(}p_{i},t_{j}\big{)}=-w\big{(}p_{i},t_{j}\big{)}\) if \(t_{j}\in p_{i}^{(t)}\), else 0. Where \(w:F\rightarrow\mathbb{N}\) is a valuation function of arcs. \(F\subseteq(T\times P)\cup(P\times T)\): Finite set of arcs. A Petri net is k-bounded if the number of tokens in each place does not exceed k. If k = 1, then the PN is said safe. A PN is live if all transitions are live; a transition is said live if it can always be made enabled starting from any reachable marking. A PN is reversible if from any reachable state \(M\) there is an enabled sequence to return to the initial marking \(M_{0}\). Let us consider a set of legal markings; such admissible states correspond to a set of general mutual exclusion constraints GMECs. A constraint \(\left(\overrightarrow{w},K\right)\) defines a set of legal markings [26]:  
\[M_{(\overrightarrow{w},k)}=\left\{M\in M\left|\overrightarrow{w}^{T}M\leq K\right\}\right. \tag{2}\]  
A new type of control specification constraint based on sequence transitions is developed in our previous work. This method is called admissible paths constraints APC \(\left(\overrightarrow{\
u},C\right)\) which defines a set of legal sequences of transitions [27]:  
\[T_{(\overrightarrow{\sigma},C)}=\left\{\sigma\in\sigma^{*}\left|\overrightarrow {v}^{T}\overrightarrow{\sigma}\leq C\right\}\right. \tag{3}\]  
The theory of regions in control synthesis was proposed by [PERSON] et al. [8; 9] using the properties of PN for adding a controller \(P_{c}\) to the initial PN model. The PN controller is characterized by its initial marking \(M_{0}(P_{c})\) and incidence vector \(C(P_{c},.)\).