Systèmes d'addition vectorielle avec des «obstacles» finis

Un système d'addition vectorielle (VAS) est un ensemble fini d' actions $A \subset \mathbb{Z}^d$ . $\mathbb{N}^d$ est l'ensemble des marquages . Une course est un mot non vide de marques $m_0 m_1\dots m_n$ st $\forall i \in \{0, \dots, n-1\}, m_{i+1}-m_i \in A$ . Si un tel mot existe, nous disons que $m_n$ est accessible à partir de $m_0$ .

Le problème de l'accessibilité des VAS est connu pour être décidable (mais sa complexité est un problème ouvert).

Supposons maintenant qu'un ensemble fini de marquages ​​interdits (les obstacles ) soit donné. Je voudrais savoir si le problème de l'accessibilité est encore décidable.

Intuitivement, l'ensemble fini d'obstacles ne devrait interférer avec les trajets que localement, de sorte que le problème devrait rester décidable. Mais il ne semble pas trivial de le prouver.

MODIFIER . Je garderai la réponse de @ Jérôme comme étant acceptée, mais je voudrais ajouter une question de suivi: que se passe-t-il si l'ensemble des marquages ​​est $\mathbb{Z}^d$ ?

L'idée est basée sur une discussion que j'ai eue avec Grégoire Sutre cet après-midi.

Le problème est décidable comme suit.

Un filet de Petri est un ensemble fini de paires dans N d × N d appelées transitions. Étant donné une transition t = ( → u , → v ) , nous notons t → la relation binaire définie sur l'ensemble des configurations N d par → x t → → y s'il existe un vecteur → z ∈ N d tel que → x = → u + → z et$T$$\mathbb{N}^d\times\mathbb{N}^d$$t=(\vec{u},\vec{v})$$\xrightarrow{t}$$\mathbb{N}^d$$\vec{x}\xrightarrow{t}\vec{y}$$\vec{z}\in\mathbb{N}^d$$\vec{x}=\vec{u}+\vec{z}$ . On note T → la relation d'accessibilité en une étape⋃t∈T t → . La fermeture réflexive et transitive de cette relation est notée T ∗ → .$\vec{y}=\vec{v}+\vec{z}$$\xrightarrow{T}$$\bigcup_{t\in T}\xrightarrow{t}$$\xrightarrow{T^*}$

Soit l'ordre partiel classique sur N d et défini par → u ≤ → x s'il existe → z ∈ N d tel que → x = → u + → z . La fermeture vers le haut d'un ensemble → X de N d est l'ensemble ↑ → X des vecteurs { → v ∈ N d ∣ ∃ → x ∈ → $\leq$$\mathbb{N}^d$$\vec{u}\leq \vec{x}$$\vec{z}\in\mathbb{N}^d$$\vec{x}=\vec{u}+\vec{z}$$\vec{X}$$\mathbb{N}^d$${\uparrow}\vec{X}$. La fermeture vers le bas d'un ensemble → X est l'ensemble↓ → X des vecteurs{ → v ∈Nd∣∃ → x ∈ → x$\{\vec{v}\in\mathbb{N}^d \mid \exists \vec{x}\in\vec{X}.\,\vec{x}\leq\vec{v}\}$$\vec{X}$${\downarrow}\vec{X}$.$\{\vec{v}\in\mathbb{N}^d \mid \exists \vec{x}\in\vec{x}.\,\vec{v}\leq\vec{x}\}$

Notez que si pour un ensemble fini → B de N d et si T est un réseau de Petri, nous pouvons calculer un nouveau réseau de Petri T → B tel que pour toutes les configurations → x , → y , nous avons → x T → → y et → x , → y ∈ → U si, et seulement si, → x T → B → → $\vec{U}={\uparrow}\vec{B}$$\vec{B}$$\mathbb{N}^d$$T$$T_{\vec{B}}$$\vec{x},\vec{y}$$\vec{x}\xrightarrow{T}\vec{y}$$\vec{x},\vec{y}\in\vec{U}$$\vec{x}\xrightarrow{T_{\vec{B}}}\vec{y}$$t=(\vec{u},\vec{v})$$\vec{b}\in\vec{B}$$t_{\vec{b}}=(\vec{u}+\vec{z},\vec{v}+\vec{z})$$\vec{z}$$\mathbb{N}^d$1≤i≤dT → U ={t → b ∣t∈$\vec{z}(i)=\max\{\vec{b}(i)-\vec{u}(i),\vec{b}(i)-\vec{v}(i),0\}$$1\leq i\leq d$$T_{\vec{U}}=\{t_{\vec{b}} \mid t\in T\,\vec{b}\in\vec{B}\}$ satisfait à l'exigence.

Supposons maintenant que soit un réseau de Petri, l'ensemble d'obstacles. Nous introduisons l'ensemble fini . Observez que nous pouvons calculer efficacement un ensemble fini de tel que . Soit la relation binaire définie sur par if , ou s'il existe telle sorte que→ O → D = ↓ → O → B N d ↑ → B = N d ∖ → D R N d ∖ → O → x R → y → x = → y → x ′ , → y ′ ∈ N d ∖ → O → x T → → x ′ T ∗ $T$$\vec{O}$$\vec{D}={\downarrow}\vec{O}$$\vec{B}$$\mathbb{N}^d$${\uparrow}\vec{B}=\mathbb{N}^d\backslash\vec{D}$$R$$\mathbb{N}^d\backslash \vec{O}$$\vec{x} R \vec{y}$$\vec{x}=\vec{y}$$\vec{x}',\vec{y}'\in \mathbb{N}^d\backslash \vec{O}$$\vec{x}\xrightarrow{T}\vec{x}'\xrightarrow{T_{\vec{B}}^*}\vec{y}'\xrightarrow{T}\vec{y}$.

Maintenant, observez simplement que s'il existe une exécution de la configuration initiale à la configuration finale qui évite l'obstacle , alors il en existe une qui évite l'obstacle dans et qui passe par des configurations dans au plus le cardinal de cet ensemble. Par conséquent, le problème se réduit à sélectionner des configurations distinctes non déterministes dans , corriger comme la configuration initiale , comme la dernière , et vérifiez que→ y → O → O → D ∖ → O → c 1,…, → c n → D ∖ → O → c 0 → x cn+1 → y → c jR → c j+1$\vec{x}$$\vec{y}$$\vec{O}$$\vec{O}$$\vec{D}\backslash \vec{O}$$\vec{c}_1,\ldots,\vec{c}_n$$\vec{D}\backslash \vec{O}$$\vec{c}_0$$\vec{x}$$c_{n+1}$$\vec{y}$$\vec{c}_j R \vec{c}_{j+1}$ pour chaque . Ce dernier problème se réduit aux questions classiques d'accessibilité pour les réseaux de Petri.$j$

J'ai réfléchi à votre question sur les systèmes d'addition vectorielle avec des états (VASS) équivalents à VAS et j'ai trouvé cette solution. Maintenant, j'ai lu la belle réponse de Jérôme et je dois dire que ma réponse est très similaire, alors veuillez accepter sa réponse même si vous considérez la mienne comme correcte.

Idée: Il est possible de convertir un VASS en un VASS qui interdit les vecteurs plus petits ou égaux aux obstacles. Ce n'est pas exactement ce que nous voulons, car les vecteurs plus petits mais pas égaux aux obstacles peuvent être atteints. Cependant, il existe de nombreux vecteurs de ce type. Cela permet une décomposition des séries minimales en plusieurs séries finies qui sont soit une transition de soit une série équivalente de . Par conséquent, oui , le problème est décidable.V ′ V V $V$$V'$$V$$V'$

Détails: Soit soit un -VASS, à savoir est un graphique marqué au fini de telle sorte que . Soit l'ensemble des obstacles. Soit et , nous écrivons chaque fois que est un courir à partir à avec chaque configuration intermédiaire . Nous dénotonsd V T ⊆ Q × Z d × Q O ⊆ N d tc ∈ T * X ⊆ N$V=(Q,T)$$d$$V$$T \subseteq Q \times \mathbb{Z}^d \times Q$$O \subseteq \mathbb{N}^d$$\pi ­\in T^*$$X \subseteq \mathbb{N}^d$$p(\boldsymbol{u}) \xrightarrow{\pi}_X q(\boldsymbol{v})$$\pi$$p(\boldsymbol{u})$$q(\boldsymbol{v})$$Q \times X$${\downarrow}X = \{\boldsymbol{y} : \boldsymbol{y} \leq \boldsymbol{x} \text{ for some } \boldsymbol{x} \in X\}$ .

Soit une course minimale telle que , c'est-à-dire une course minimale qui évite les obstacles. Ensuite, par le principe du pigeonhole, peut être factorisé comme une course qui n'entre que plusieurs fois de façon finie. Plus formellement, il existe , et tel que$\pi$$p(\boldsymbol{u}) \xrightarrow{\pi}_{\mathbb{N}^d \setminus O} q(\boldsymbol{v})$$\pi$${\downarrow}O \setminus O$$t_1, t_1' \ldots, t_{n+1}, t_{n+1}' \in T \cup \{\varepsilon\}$$\pi_1, \ldots, \pi_{n+1} \in T^*$$\{p_i(\boldsymbol{u}_i), q_i(\boldsymbol{v}_i), r_i(\boldsymbol{w}_i)\}_{i \in [0,n+1]} \subseteq Q \times \mathbb{N}^d$

• $\pi = t_1 \pi_1 t_1' \cdots t_{n+1} \pi_{n+1} t_{n+1}'$ ,
• $\forall i \in [0,n]\ \; p_i(\boldsymbol{u}_i) \xrightarrow{t_{i+1}}_{\mathbb{N}^d} q_{i+1}(\boldsymbol{v}_{i+1}) \xrightarrow{\pi_{i+1}}_{\mathbb{N}^d \setminus {\downarrow}O} r_{i+1}(\boldsymbol{w}_{i+1}) \xrightarrow{t_{i+1}'}_{\mathbb{N}^d} p_{i+1}(\boldsymbol{u}_{i+1})$
• $p_0(\boldsymbol{u}_0) = p(\boldsymbol{u}),\ p_{n+1}(\boldsymbol{u}_{n+1}) = q(\boldsymbol{v})$ ,
• $\forall i \in [1,n]\ \; \boldsymbol{u}_i \in {\downarrow}O \setminus O$ .
• $n \leq |Q| \cdot |{\downarrow}O|$.

Par conséquent, il suffit de deviner , et les configurations intermédiaires. Tester si peut être effectué en convertissant en un nouveau -VASS où chaque transition est remplacée par un gadget de transitions. Par exemple, si alors les transitions sont remplacées comme suit:$n$$t_1, t_1', \ldots, t_{n+1}, t_{n+1}'$$p(\boldsymbol{x}) \xrightarrow{*}_{\mathbb{N}^d \setminus {\downarrow}O} q(\boldsymbol{y})$$V$$d$$V'$$t \in T$$4|O|+1$$O = \{(1,5), (2,3)\}$