Systemy dodawania wektorów ze skończonymi „przeszkodami”

System dodawania wektorów (VAS) to skończony zestaw działań . jest zbiorem oznaczeń . Trasa jest niepusty słowo oznaczenia st . Jeśli takie słowo istnieje, mówimy, że jest osiągalne z .$A \subset \mathbb{Z}^d$m 0 m 1 … m n ∀ i ∈ { 0 , … , n - 1 } , m i + 1 - m i ∈ A m n m $\mathbb{N}^d$$m_0 m_1\dots m_n$$\forall i \in \{0, \dots, n-1\}, m_{i+1}-m_i \in A$$m_n$$m_0$

Problem osiągalności VAS jest znany z rozstrzygania (ale jego złożoność jest problemem otwartym).

Załóżmy teraz, że podano skończony zestaw zabronionych oznaczeń ( przeszkód ). Chciałbym wiedzieć, czy problem osiągalności jest nadal rozstrzygalny.

Intuicyjnie skończony zestaw przeszkód powinien zakłócać ścieżki tylko lokalnie, więc problem powinien pozostać rozstrzygalny. Ale udowodnienie tego nie wydaje się trywialne.

EDYCJA . Zachowam odpowiedź @ Jérôme jako zaakceptowaną, ale chciałbym dodać kolejne pytanie: co jeśli zestaw oznaczeń to ?$\mathbb{Z}^d$

Pomysł opiera się na dyskusji, którą przeprowadziłem dziś po południu z Grégoire Sutre.

Problem można rozstrzygnąć w następujący sposób.

Siatka Petriego to skończony zestaw par w zwanych przejściami. Biorąc pod uwagę przejście , oznaczamy przez relację binarną zdefiniowaną w zbiorze konfiguracji przez jeśli istnieje wektor taki, że i . przez relację osiągalności w jednym kroku . Refleksyjne i przechodnie zamknięcie tej relacji jest oznaczone symbolemN d × N d t = ( → u , → v$T$$\mathbb{N}^d\times\mathbb{N}^d$$t=(\vec{u},\vec{v})$Nd → x t → → y → z ∈Nd → x = → u + → z → y = → v + → z T →⋃t∈T t → T ∗$\xrightarrow{t}$$\mathbb{N}^d$$\vec{x}\xrightarrow{t}\vec{y}$$\vec{z}\in\mathbb{N}^d$$\vec{x}=\vec{u}+\vec{z}$$\vec{y}=\vec{v}+\vec{z}$$\xrightarrow{T}$$\bigcup_{t\in T}\xrightarrow{t}$$\xrightarrow{T^*}$ .

Niech będzie klasyczną składową częściową kolejnością nad i zdefiniowaną przez jeśli istnieje taki że . Zamknięcie w górę zbioru z jest zbiorem wektorów . Zamknięcie w dół zbioru to zbiór wektorów .N d → U ≤ → x → z ∈ N d → x = → U + → z → X N d ↑ Ilość → X { → v ∈ N d | ∃ → x ∈ → 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}$ → X ↓ → X { → 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}\}$

Zauważ, że jeśli dla jakiegoś skończonego zestawu z a jeśli jest siecią Petriego, możemy obliczyć nową sieć Petriego taki, że dla każdej konfiguracji mamy i if i tylko jeśli, . W rzeczywistości, jeśli jest przejściem, to dla każdego , niech gdzie to wektor w→ B NdTT → B → x , → $\vec{U}={\uparrow}\vec{B}$$\vec{B}$$\mathbb{N}^d$$T$$T_{\vec{B}}$$\vec{x},\vec{y}$→ x , → y ∈ → U → x T → B → → y t=( → u , → v ) → b ∈ → B t → b =($\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}$ → z Nd → z (i)=max{ → b (i)- → u (i), → b (i)- → v (i),0}1≤i≤dT → U ={t$t_{\vec{b}}=(\vec{u}+\vec{z},\vec{v}+\vec{z})$$\vec{z}$$\mathbb{N}^d$ zdefiniowany komponentowo przez dla każdego . Zauważ, że spełnia to wymaganie.$\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}\}$

Załóżmy teraz, że jest siecią Petriego, zestawem przeszkód. Przedstawiamy zestaw skończony . Zauważ, że możemy skutecznie obliczyć skończony zbiór z taki, że . Niech będzie relacją binarną zdefiniowaną przez przez if , lub istnieje taki, że→ O → D = ↓ → O → B N d ↑ → B = $T$$\vec{O}$$\vec{D}={\downarrow}\vec{O}$$\vec{B}$$\mathbb{N}^d$ R N d ∖ → O → x R → y → x = → y → x ′ , → y ′ ∈ N d ∖ → O → x T → → x ′ T ∗ ${\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}$.

Teraz zauważ, że jeśli istnieje bieg od konfiguracji początkowej do wersji końcowej która omija przeszkodę , wtedy istnieje taki, który omija przeszkodę w i to przechodzi przez konfiguracje w co najwyżej kardynał tego zestawu. W związku z tym problem ogranicza się do wybierania niedeterministycznie odrębnych konfiguracji w , fix jako początkowa konfiguracja , jako ostateczna i sprawdź, czy→ y → O → O → D ∖ → O → c 1,…, → c n → $\vec{x}$$\vec{y}$$\vec{O}$$\vec{O}$$\vec{D}\backslash \vec{O}$$\vec{c}_1,\ldots,\vec{c}_n$→ c 0 → x c n + 1 → y → c j R → c j + 1$\vec{D}\backslash \vec{O}$$\vec{c}_0$$\vec{x}$$c_{n+1}$$\vec{y}$$\vec{c}_j R \vec{c}_{j+1}$ dla każdego . Ten ostatni problem ogranicza się do klasycznych pytań dotyczących osiągalności sieci Petriego.$j$

Zastanawiałem się nad twoim pytaniem dotyczącym systemów dodawania wektorów ze stanami (VASS), które są równoważne VAS i wymyśliłem to rozwiązanie. Teraz przeczytałem miłą odpowiedź Jérôme'a i muszę powiedzieć, że moja odpowiedź jest bardzo podobna, więc proszę przyjąć jego odpowiedź, nawet jeśli uważasz, że moja jest poprawna.

Pomysł: Możliwe jest przekształcenie VASS w VASS który zabrania wektorów mniejszych lub równych przeszkodom. Nie jest to dokładnie to, czego chcemy, ponieważ dozwolone są wektory mniejsze, ale nie równe przeszkodom. Istnieje jednak wiele takich wektorów. Pozwala to na rozkład minimalnych przebiegów na skończoną liczbę przebiegów, które są albo przejściem albo równoważnym przebiegiem . Dlatego tak , problem jest rozstrzygalny.V ′ V V $V$$V'$$V$$V'$

Szczegóły niech będzie -VASS, to jest ograniczony tak, że znakowane wykres . Niech będzie zbiorem przeszkód. Niech i , piszemy ilekroć jest biegną od do z każdej konfiguracji pośredniej w . Oznaczamyd V T ⊆ Q × Z d × Q O ⊆ 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\}$ .

Niech będzie minimalnym uruchomieniem, tak aby , tj. Minimalnym uruchomieniem, które omija przeszkody. Następnie, zgodnie z zasadą szufladki, można podzielić na czynniki pierwsze jako przebieg, który wchodzi tylko skończenie wiele razy. Bardziej formalnie istnieją , i takie, że$\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|$.

Dlatego wystarczy odgadnąć , i konfiguracje pośrednie. Testowanie, czy można przeprowadzić, konwertując na nowy -VASS gdzie każde przejście jest zastąpione gadżetem przejść. Na przykład, jeśli wówczas przejścia są zastępowane w następujący sposób:$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)\}$