Vektoradditionssysteme mit endlichen „Hindernissen“

11

Ein Vector Addition System (VAS) ist eine endliche Menge von Aktionen . ist der Satz von Markierungen . Ein Lauf ist ein nicht-leeres Wort von Markierungen st . Wenn ein solches Wort existiert sagen wir , dass ist erreichbar von .AZdm 0 m 1m ni { 0 , , n - 1 } , m i + 1 - m iA m n m 0Ndm0m1mni{0,,n1},mi+1miAmnm0

Das Problem der Erreichbarkeit von VAS ist bekanntermaßen entscheidbar (seine Komplexität ist jedoch ein offenes Problem).

Nehmen wir nun an, dass eine endliche Menge verbotener Markierungen (die Hindernisse ) gegeben ist. Ich würde gerne wissen, ob das Problem der Erreichbarkeit noch entscheidbar ist.

Intuitiv sollte die endliche Menge von Hindernissen die Pfade nur lokal stören, so dass das Problem entscheidbar bleiben sollte. Aber es scheint nicht trivial, es zu beweisen.

BEARBEITEN . Ich werde die Antwort von @ Jérôme als die akzeptierte beibehalten, aber ich möchte eine Folgefrage hinzufügen: Was ist, wenn der Satz von Markierungen ?Zd

Nicolas Perrin
quelle
Haben Sie eine gute Referenz, um sich ein Bild von den Ideen zu machen, die hinter dem Entscheidbarkeitsnachweis stehen? (zum Beispiel Folien)
Denis
1
Hier sind Folien: lsv.ens-cachan.fr/Events/Pavas/slides-Leroux.pdf ; und ein kürzlich veröffentlichter Artikel: hal.archives-ouvertes.fr/hal-00674970 ; Grundsätzlich wird die Erreichbarkeit durch einen Aufzählungsalgorithmus gelöst, der auf der Tatsache basiert, dass, wenn von aus nicht erreichbar ist , zwei disjunkte Presburger-Mengen existieren, die die Nichterreichbarkeit irgendwie beweisen. Einige andere Folien: automata.rwth-aachen.de/movep2010/abstracts/slides-leroux.pdf . xyx
Nicolas Perrin
M Praveen hat mehrere Vorträge über die beiden Hauptansätze des Problems gehalten: cmi.ac.in/~praveenm/talks
Sylvain
Für Teilfälle des Problems mit endlichen Hindernissen (z. B. mit eingeschränkter Dimension) scheint es, dass ein Beweis der Entscheidbarkeit auf einer "Zick-Zack-Eliminierungs" -Eigenschaft beruhen könnte. Siehe dieses Dokument : labri.fr/perso/leroux/published-papers/LS-concur04.ps und diese Folien: labri.fr/perso/sutre/Talks/Documents/… .
Nicolas Perrin
1
Ich verstehe, warum das Problem gelöst wird, wenn es Aktionen ungleich Null gibt, die sich zu Null summieren, aber was passiert, wenn solche Aktionen nicht existieren? Ein Teil Ihrer Antwort wurde aus dem Kommentar herausgeschnitten :)
Nicolas Perrin

Antworten:

5

Die Idee basiert auf einer Diskussion, die ich heute Nachmittag mit Grégoire Sutre geführt habe.

Das Problem ist wie folgt entscheidbar.

Ein Petri-Netz ist eine endliche Menge von Paaren in als Übergänge bezeichnet werden. Bei einem Übergang bezeichnen wir mit die binäre Beziehung, die in der Menge der Konfigurationen durch wenn ein Vektor existiert, so dass und . Wir bezeichnen mit die Ein-Schritt-Erreichbarkeitsrelation . Der reflexive und transitive Abschluss dieser Beziehung wird mit bezeichnetN d × N d t = ( u , v ) t N d x tyTNd×Ndt=(u,v)tNdxtyx =u +z y =v +z TtT tT zNdx=u+zy=v+zTtTtT .

Let die klassischen komponenten partielle Ordnung über seine und definiert durch , wenn es existiert solchen dass . Das Aufwärtsschließen einer Menge von ist die Menge von Vektoren . Das Abwärtsschließen einer Menge ist die Menge von Vektoren .N d uNdzNdx =u +Z X NdX {vNd|xX .uxzNdx=u+zXNdXXX {vNd|xx .{vNdxX.xv}XX{vNdxx.vx}

Beachten Sie, dass wir , wenn für eine endliche Menge von und ein Petri-Netz ist, ein neues Petri-Netz berechnen können so dass wir für jede Konfiguration und genau dann, wenn . In der Tat, wenn einen Übergang, dann für jeden , lassen wobei der Vektor in istB NdTTBx ,y x Ty x , u +z ,v +z )U=BBNdTTBx,yxTyx T By t=(u ,v )bB tb =(x,yUxTByt=(u,v)bBtb=(u+z,v+z) Ndz (i)=max{B (i)-u (i),B (i)-v (i),0}1idTU ={tzNd definiert komponentenweise durch für jede . Beachten Sie, dass die Anforderung erfüllt.z(i)=max{b(i)u(i),b(i)v(i),0}1idTU={tbtTbB}

Nehmen wir nun an, dass ein Petri-Netz ist, die Menge der Hindernisse. Wir führen die endliche Menge . Beachten Sie, dass wir eine endliche Menge von effektiv berechnen können, so dass . Sei die binäre Beziehung, die über von wenn oder existiert so dassA D = O B N d B = N dD R N dO x R Y x = Y x ' , y 'N dO x Tx ' T TOD=OBNdB=NdDRNdOxRyx=yx,yNdOxTxTByTy.

Beachten Sie nun, dass es einen Lauf von der ursprünglichen Konfiguration zur letzten , der das Hindernis umgeht, und dass es einen Lauf gibt, der das Hindernis in vermeidet und das geht an Konfigurationen in höchstens dem Kardinal dieser Menge. Daher reduziert sich das Problem auf die Auswahl nicht deterministisch unterschiedlicher Konfigurationen in , Fix as die anfängliche Konfiguration , als die endgültige , und überprüfen Sie diesy O O DO c 1,...,C nDO c 0xxyOODOc1,,cnDOc0xY c j R c j + 1 jcn+1ycjRcj+1 für jedes . Dieses letzte Problem reduziert sich auf klassische Erreichbarkeitsfragen für Petri-Netze.j

Jérôme
quelle
Super, vielen Dank!! Diese Frage kam mir regelmäßig wieder in den Sinn!
Nicolas Perrin
2
Nun mag es offensichtlich sein, aber ich möchte sicher eine Folgefrage stellen, um sicher zu sein. Was ist, wenn wir zulassen, dass die Menge der Markierungen ist? In diesem Fall funktioniert genau dieselbe Konstruktion nicht. Gibt es ein einfaches Argument, das das Ergebnis erweitert? Zd
Nicolas Perrin
4

Ich habe über Ihre Frage nach Vektoradditionssystemen mit Zuständen (VASS) nachgedacht, die VAS entsprechen, und diese Lösung gefunden. Jetzt habe ich Jérômes nette Antwort gelesen und ich muss sagen, dass meine Antwort sehr ähnlich ist. Bitte akzeptieren Sie seine Antwort, auch wenn Sie meine für richtig halten.


Idee: Es ist möglich, ein VASS in ein VASS umzuwandeln , das Vektoren verbietet, die kleiner oder gleich den Hindernissen sind. Dies ist nicht genau das, was wir wollen, da Vektoren erreicht werden dürfen, die kleiner, aber nicht gleich den Hindernissen sind. Es gibt jedoch endlich viele solcher Vektoren. Dies ermöglicht eine Zerlegung von Minimalläufen in endlich viele Läufe, die entweder ein Übergang von oder ein äquivalenter Lauf von . Daher ist das Problem ja entscheidbar.V ' V V 'VVVV


Details: Let sein -VASS, dh ist eine endliche markierte Graph , so dass . Sei die Menge der Hindernisse. Sei und , wir schreiben wann immer ist Führen Sie mit jeder Zwischenkonfiguration in von nach . Wir bezeichnend 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} .

Sei ein minimaler Lauf, so dass , dh ein minimaler Lauf, der vermeidet die Hindernisse. Dann kann nach dem Pigeonhole-Prinzip als ein Lauf faktorisiert werden, der nur endlich viele Male in eintritt . Formal gibt es , und so dassπ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|.

Daher reicht es aus, , und die Zwischenkonfigurationen zu erraten . Testen, ob kann, indem in ein neues konvertiert wird VASS wobei jeder Übergang durch ein Gadget von Übergängen ersetzt wird. Wenn beispielsweise die Übergänge wie folgt ersetzt:nt1,t1,,tn+1,tn+1p(x)NdOq(y)VdVtT4|O|+1O={(1,5),(2,3)}VASS-Gerät

Michael Blondin
quelle
1
Vielen Dank!! Zwei richtige Antworten in weniger als 2 Tagen, ich muss sagen, dass diese Community gut funktioniert :)
Nicolas Perrin