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

11

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 .AZdm 0 m 1m ni { 0 , , n - 1 } , m i + 1 - m iA m n m 0Ndm0m1mni{0,,n1},mi+1miAmnm0

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 ?Zd

Nicolas Perrin
źródło
czy masz dobre referencje, aby poznać intuicję pomysłów leżących u podstaw dowodu rozstrzygalności? (na przykład slajdy)
Denis
1
Oto slajdy: lsv.ens-cachan.fr/Events/Pavas/slides-Leroux.pdf ; oraz najnowszy artykuł: hal.archives-ouvertes.fr/hal-00674970 ; w zasadzie osiągalność jest rozwiązana przez algorytm wyliczenia, oparty na fakcie, że jeśli nie jest osiągalne z , to istnieją dwa rozłączne zestawy Presburger, które w jakiś sposób dowodzą nieosiągalności. Niektóre inne slajdy: automata.rwth-aachen.de/movep2010/abstracts/slides-leroux.pdf . yx
Nicolas Perrin
M. Praveen wygłosił kilka rozmów na temat dwóch głównych podejść do problemu: cmi.ac.in/~praveenm/talks
Sylvain
W przypadku podklas problemu z ograniczeniami skończonymi (np. O ograniczonym wymiarze) wydaje się, że dowód rozstrzygalności może być oparty na właściwości „eliminacji zygzaków”. Zobacz ten artykuł: labri.fr/perso/leroux/published-papers/LS-concur04.ps i te slajdy: labri.fr/perso/sutre/Talks/Documents/… .
Nicolas Perrin
1
Rozumiem, dlaczego problem został rozwiązany, gdy istnieją niezerowe akcje, które sumują się do zera, ale co się dzieje, gdy takie działania nie istnieją? Część twojej odpowiedzi została odcięta od komentarza :)
Nicolas Perrin

Odpowiedzi:

5

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 )TNd×Ndt=(u,v)Ndx ty zNdx =u +z y =v +z TtT t T tNdxtyzNdx=u+zy=v+zTtTtT .

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 Ux zN d x = U + z X N d ↑ Ilość X { vN d | xX .NduxzNdx=u+zXNdXXX {vNdxx .{vNdxX.xv}XX{vNdxx.vx}

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 wB NdTTBx ,yU=BBNdTTBx,yx ,yU x T By t=(u ,v )bB tb =(xTyx,yUxTByt=(u,v)bBz Ndz (i)=max{b (i)-u (i),b (i)-v (i),0}1idTU ={ttb=(u+z,v+z)zNd zdefiniowany komponentowo przez dla każdego . Zauważ, że spełnia to wymaganie.z(i)=max{b(i)u(i),b(i)v(i),0}1idTU={tbtTbB}

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, żeO D = O B N d B = NTOD=OBNd R N dO x R y x = y x , yN dO x TxT B=NdDRNdOxRyx=yx,yNdOxTxTByTy.

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ź, czyy O O DO c 1,,c nDxyOODOc1,,cnc 0 x c n + 1 y c j R c j + 1 jDOc0xcn+1ycjRcj+1 dla każdego . Ten ostatni problem ogranicza się do klasycznych pytań dotyczących osiągalności sieci Petriego.j

Jérôme
źródło
Wielkie dzięki!! To pytanie okresowo wracało mi do głowy!
Nicolas Perrin
2
Teraz może to być oczywiste, ale z pewnością chciałbym zadać pytanie uzupełniające. Co jeśli pozwolimy być zestawem oznaczeń? W takim przypadku dokładnie ta sama konstrukcja nie działa. Czy istnieje prosty argument, który rozszerza wynik? Zd
Nicolas Perrin
4

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 VVVV


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 dV=(Q,T)dVTQ×Zd×QONdπ­TXNdp(u)πXq(v)πp(u)q(v)Q×XX={y:yx for some xX} .

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πp(u)πNdOq(v)πOOt1,t1,tn+1,tn+1T{ε}π1,,πn+1T{pi(ui),qi(vi),ri(wi)}i[0,n+1]Q×Nd

  • π=t1π1t1tn+1πn+1tn+1 ,
  • i[0,n] pi(ui)ti+1Ndqi+1(vi+1)πi+1NdOri+1(wi+1)ti+1Ndpi+1(ui+1)
  • p0(u0)=p(u), pn+1(un+1)=q(v) ,
  • i[1,n] uiOO .
  • n|Q||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:nt1,t1,,tn+1,tn+1p(x)NdOq(y)VdVtT4|O|+1O={(1,5),(2,3)}Gadżet VASS

Michael Blondin
źródło
1
Dzięki!! Dwie poprawne odpowiedzi w mniej niż 2 dni, muszę powiedzieć, że ta społeczność działa dobrze :)
Nicolas Perrin