Skillnadsbunden matris

I modellkontroll , ett område inom datavetenskap , är en skillnadsbunden matris (DBM) en datastruktur som används för att representera några konvexa polytoper som kallas zoner . Denna struktur kan användas för att effektivt implementera vissa geometriska operationer över zoner, såsom att testa tomhet, inkludering, jämlikhet och beräkna skärningspunkten och summan av två zoner. Det används till exempel i Uppaal modellchecker ; där det också distribueras som ett fristående bibliotek.

Mer exakt finns det en föreställning om kanonisk DBM; det finns en en-till-en-relation mellan kanoniska DBM och zoner och från varje DBM kan en kanonisk ekvivalent DBM effektivt beräknas. Sålunda kan zonlikhet testas genom att kontrollera om kanoniska DBM:er är lika.

Zon

En differensbunden matris används för att representera någon form av konvexa polytoper. Dessa polytoper kallas zon . De är nu definierade. Formellt definieras en zon av ekvationer av formen $x\leq c$ , $x\geq c$ , $x_{1}\ leq x_{2}+c$ och $x_{1}\geq x_{2}+c$ , med $x_{1}$ och $x_{2}$ vissa variabler, och $c$ en konstant.

Zoner har ursprungligen kallats region , men nuförtiden betecknar detta namn vanligtvis region , en speciell sorts zon. Intuitivt kan en region betraktas som en minimal icke-tom zon, där de konstanter som används i tvång är avgränsade.

Givet $n$ variabler finns det exakt $n(n+1)$ olika icke-redundanta begränsningar möjliga, $n$ begränsningar som använder en enskild variabel och en övre bundna, $n$ begränsningar som använder en enskild variabel och en nedre gräns, och för var och en av de $n^{2}$ ordnade paren av variabel $(x, y)$ , en övre gräns på $xy$ . En godtycklig konvex polytop i $\mathbb {R} ^{n}$ kan dock kräva ett godtyckligt stort antal begränsningar. Även när $n=2$ , kan det finnas ett godtyckligt stort antal icke-redundanta begränsningar $(x<iy+c_{i}) _{i\in \mathbb {N} }$ , för $c_{i}$ några konstanter. Detta är anledningen till att DBM inte kan utökas från zoner till konvexa polytoper.

Exempel

Som nämnts i inledningen betraktar vi en zon definierad av en uppsättning satser av formen ${\displaystyle x_{1}\leq c} ,$ x $\displaystyle x_{1}\geq c}$ , $x_{1}\leq x_{2}+c$ och $x_{1}\geq x_{2}+c$ , med $x_{1}$ och $x_{2}$ några variabler, och $c$ en konstant. Men några av dessa begränsningar är antingen motsägelsefulla eller överflödiga. Vi ger nu sådana exempel.

• begränsningarna $x_{1}\leq 3$ och $x_{1}\geq 4$ är ​​motsägelsefulla. När två sådana begränsningar hittas är den definierade zonen tom.
  

  Figur i ${\textstyle \mathbb {R} ^{2}}$ som visar ${\textstyle x_{1}\leq 3}$ , ${\textstyle x_{1}\geq 4}$ som är osammanhängande
• begränsningarna $x_{1}\leq 3$ och $x_{1}\leq 4$ är ​​redundanta. Den andra begränsningen antyds av den första. När två sådana begränsningar hittas i definitionen av zonen kan den andra begränsningen därför tas bort.
  

  Figur i ${\textstyle \mathbb {R} ^{2}}$ som visar ${\textstyle x_{1}\leq 3}$ och ${\textstyle x_{1}\leq 4}$ som innehåller den första figuren

Vi ger också exempel som visar hur man genererar nya begränsningar från befintliga begränsningar. För varje par av klockor $x_{1}$ och $x_{2}$ har DBM en begränsning av formen $x_{1}\ prec x_{2}+c$ , där $\prec$ är antingen < eller ≤. Om ingen sådan begränsning kan hittas, kan begränsningen $x_{1}\prec x_{2}+\infty$ läggas till i zondefinitionen utan förlust av generalitet. Men i vissa fall kan en mer exakt begränsning hittas. Ett sådant exempel kommer nu att ges.

• begränsningarna $x_{1}\leq 3$ , $x_{2}\geq -3$ innebär att $x_{1 }\leq x_{2}+6$ . Alltså, förutsatt att ingen annan begränsning som $x_{1}\leq x_{2}+5$ eller $x_{1}<x_{ 2}+6$ tillhör definitionen, begränsningen $x_{1}\leq x_{2}+6$ läggs till zondefinitionen.
  

  Figur i ${\textstyle \mathbb {R} ^{2}}$ som visar ${\textstyle x_{1}\leq 3}$ , ${\textstyle x_{2}\geq -3 }$ och deras korsningar
• begränsningarna $x_{2}\leq 3$ , $x_{1}\leq x_{2}+3$ innebär att $x_{1}\leq 6$ . Om man antar att ingen annan begränsning såsom $x_{1}\leq 5$ eller $x_{1}<6$ tillhör definitionen, så hör begränsningen $x_{1}\leq 6$ läggs till i zondefinitionen.
  

  Figur i ${\textstyle \mathbb {R} ^{2}}$ som visar ${\textstyle x_{1}\leq 3}$ , ${\textstyle x_{1}\leq x_{2}+3}$ och deras korsningar
• begränsningarna $x_{1}\leq x_{2}+3$ , $x_{2}\leq x_{3}+3$ antyder att $x_{1}\leq x_{3}+6$ . Alltså, förutsatt att ingen annan begränsning som $x_{1}\leq x_{3}+5$ eller $x_{1}<x_{ 3}+6$ tillhör definitionen, begränsningen $x_{1}\leq x_{3}+6$ läggs till zondefinitionen.

Egentligen är de två första fallen ovan särskilda fall av de tredje fallen. Faktum är att $x_{1}\leq 3$ och $x_{2}\geq -3$ kan skrivas om som $x_{1 }\leq 0+3$ respektive $0\leq x_{2}+3$ . Och följaktligen liknar begränsningen $x_{1}\leq x_{2}+6$ som lagts till i det första exemplet den begränsning som lagts till i det tredje exemplet.

Definition

Vi fixar nu en monoid $(M,0,+)$ som är en delmängd av den reella linjen. Denna monoid är traditionellt sett uppsättningen av heltal , rationaler , reella eller deras delmängd av icke-negativa tal.

Begränsningar

För att definiera datastrukturens skillnadsbundna matris , krävs det först att ge en datastruktur för att koda atomära begränsningar. Dessutom introducerar vi en algebra för atomära begränsningar. Denna algebra liknar den tropiska semiringen , med två modifieringar:

• En godtyckligt ordnad monoid kan användas istället för ℝ.
• För att kunna skilja mellan " $<m$ " och " $\leq m$ " måste uppsättningen av element i algebra innehålla information som anger om ordningen är strikt eller inte.

Definition av begränsningar

Uppsättningen av tillfredsställande begränsningar definieras som uppsättningen av par av formuläret:

• $(\leq ,m)$ , med $m\in M$ , som representerar en begränsning av formen $\leq m$ ,
• $(<,m)$ , med $m\in M$ , där $m$ inte är ett minimalt element av $M$ , som representerar en begränsning av formen $<m$ ,
• $(<,\infty )$ , som representerar frånvaron av begränsning.

Uppsättningen av begränsningar innehåller alla tillfredsställande begränsningar och innehåller även följande otillfredsställande begränsning:

• $(<,-\infty )$ .

Delmängden $\{q\in \mathbb {Q} \mid q\leq {\sqrt {2}}\}$ kan inte definieras med denna typ av begränsningar. Mer generellt kan vissa konvexa polytoper inte definieras när den ordnade monoiden inte har den minst övre bundna egenskapen, även om var och en av begränsningarna i dess definition använder högst två variabler.

Operation på begränsningar

För att generera en enda begränsning från ett par begränsningar som tillämpas på samma (par av) variabel, formaliserar vi begreppet skärningspunkt mellan begränsningar och ordning över begränsningar. På liknande sätt, för att definiera nya begränsningar från befintliga begränsningar, måste en begreppet summa av begränsning också definieras.

Ordning om begränsningar

Vi definierar nu en orderrelation över begränsningar. Denna ordning symboliserar inkluderingsrelationen.

betraktas mängden ${\displaystyle \{<,\leq \}} som en ordnad mängd, där < är sämre än ≤.$ Intuitivt väljs denna ordning eftersom mängden som definieras av $x<c$ strikt ingår i mängden som definieras av $x\leq c$ . Vi anger sedan att begränsningen $(\prec _{1},m_{1})$ är mindre än $(\prec _{2} ,m_{2})$ om antingen $m_{1}<m_{2}$ eller ( $m_{1}=m_{2}$ och $\prec _{1}$ är mindre än ${\displaystyle \prec _{2}} )$ . Det vill säga, ordningen på begränsningar är den lexikografiska ordningen som tillämpas från höger till vänster. Observera att denna order är en total order . Om $M$ har den minst-upper-bound-egenskapen (eller greatest-lower-bound-egenskapen ) så har uppsättningen av begränsningar det också.

Skärning av begränsningar

Skärningen mellan två begränsningar, betecknad som $(\prec _{1},m_{1})\sqcap (\prec _{2},m_ {2})$ , definieras då helt enkelt som minimum av dessa två begränsningar. Om $M$ har egenskapen störst-undre gräns definieras också skärningspunkten för ett oändligt antal begränsningar.

Summan av begränsningar

Givet två variabler $x_{1}$ och $x_{2}$ som tillämpas begränsningar $(\prec _{1},m_{1 })$ och $(\prec _{2},m_{2})$ , förklarar vi nu hur man genererar begränsningen som uppfylls av $x_{1 }+x_{2}$ . Denna begränsning kallas summan av de två ovan nämnda begränsningarna, betecknas som $(\prec _{1},m_{1})+( \prec _{2},m_{2})$ och definieras som $(\min(\prec _{1},\prec _ {2}),m_{1}+m_{2})$ .

Restriktioner som en algebra

Här är en lista över algebraiska egenskaper som uppfylls av uppsättningen av begränsningar.

• Båda operationerna är associativa och kommutativa ,
• Summan är distributiv över skärningspunkten, det vill säga för alla tre begränsningar, ${\displaystyle ((\prec _{1} ,m_{1})\sqcap (\prec _{2},m_{2}))+(\prec _{3},m_{3})} är lika$ med $((\prec _{1},m_{1})+(\prec _{3},m_ {3}))\sqcap ((\prec _{2},m_{2})+(\prec _{3},m_{3}))$ ,
• Korsningsoperationen är idempotent,
• Begränsningen $(<,\infty )$ är en identitet för korsningsoperationen,
• Begränsningen $(\leq ,0)$ är en identitet för summaoperationen,

Dessutom gäller följande algebraiska egenskaper över tillfredsställande begränsningar:

• Begränsningen $(<,\infty )$ är en nolla för summaoperationen,
• Det följer att uppsättningen av tillfredsställbara begränsningar är en idempotent semiring , med $(<,\infty )$ som noll och $(\leq ,0)$ som enhet.
• Om 0 är minimielementet för $M$ så är $(\leq ,0)$ en nolla för skärningsbegränsningarna över tillfredsställbara begränsningar.

Över icke-tillfredsställande begränsningar har båda operationerna samma nolla, vilket är $(<,-\infty )$ . Således bildar uppsättningen av begränsningar inte ens en semiring, eftersom identiteten för skärningspunkten är skild från summans noll.

DBM:er

Givet en uppsättning av $n$ variabler, $x_{1},\dots ,x_{n}$ , är en DBM en matris med kolumn och rader indexerade med $0,x_{1},\dots ,x_{n}$ och posterna är begränsningar. Intuitivt, för en kolumn $C$ och en rad ${\displaystyle R} ,$ representerar värdet $m$ vid position $(C,R)$$C\prec R+m$ . Således, zonen som definieras av en matris ${\displaystyle D((\prec _{C,R} ,m_{C,R}))_{C,R\in \{0,x_{1},\dots ,x_{n}}\}} , betecknad med R ( D ) {$ \ ${ R}}(D)}$${ \displaystyle \{(x_{1},\dots ,x_{n})\in \mathbb {R} \mid \bigwedge _{C,R\in \{0,x_{1},\dots ,x_{ n}\}}C\prec _{C,R}R+m_{C,R}\}}$ är .

Observera att $C\prec R+m$ är ekvivalent med $CR\prec m$ , alltså posten $(\prec ,m )$ är fortfarande i huvudsak en övre gräns. Observera dock att eftersom vi betraktar en monoid $M$ , för vissa värden på $C$ och ${\displaystyle R} tillhör$ den verkliga $CR$ faktiskt inte monoiden .

Innan vi introducerar definitionen av en kanonisk DBM måste vi definiera och diskutera en ordningsrelation på dessa matriser.

Beställ på de matriserna

En matris $D$ anses vara mindre än en matris $D'$ om var och en av dess poster är mindre. Observera att denna order inte är total. Givet två DBM:er $D$ och $D'$ , om $D$ är mindre än eller lika med $D'$ , då ${\mathcal {R}}(D)\subseteq {\mathcal {R}}(D')$ .

Den största-undre gränsen av två matriser $D$ och $D'$ , betecknad med $D\sqcap D'$ , har som sin ${ \displaystyle (a,b)}$ ange värdet $(\prec _{a,b},m_ {a,b})\sqcap (\prec '_{a,b},m'_{a,b})$ . Notera att eftersom $\sqcap$ är «summa»-operationen för semiring av restriktioner, är operationen $\sqcap$ «summan» av två DBM:er där uppsättningen DBM:er betraktas som en modul .

På samma sätt som fallet med begränsningar, som betraktas i avsnittet "Operation på begränsningar" ovan, är den största-undre gränsen för ett oändligt antal matriser korrekt definierad så snart som $M$ uppfyller den största-undre gränsen egenskapen.

Skärningspunkten mellan matriser/zoner definieras. Den fackliga verksamheten är inte definierad, och en förening av zon är faktiskt inte en zon i allmänhet.

För en godtycklig uppsättning ${\mathcal {D}}$ av matriser som alla definierar samma zon $Z$ , $\sqcap _{D\in {\mathcal { D}}}D$ definierar också $Z$ . Det följer sålunda att så länge som $M$ har den största-nedre-gräns-egenskapen, har varje zon som definieras av åtminstone en matris en unik minimal matris som definierar den. Denna matris kallas den kanoniska DBM för $Z$ .

Första definitionen av kanonisk DBM

Vi upprepar definitionen av en kanonisk skillnadsbunden matris . Det är en DBM så att ingen mindre matris definierar samma uppsättning. Det förklaras nedan hur man kontrollerar om en matris är en DBM, och i övrigt hur man beräknar en DBM från en godtycklig matris så att båda matriserna representerar samma mängd. Men först ger vi några exempel.

Exempel på matriser

Vi överväger först fallet där det finns en enda klocka $x_{1}$ .

Den riktiga linjen

Vi ger först den kanoniska DBM för $\mathbb {R}$ . Vi introducerar sedan en annan DBM som kodar uppsättningen $\mathbb {R}$ . Detta gör det möjligt att hitta begränsningar som måste uppfyllas av alla DBM.

Den kanoniska DBM för mängden reella är $\left({\begin{array}{ll}(\leq ,0) &(<,\infty )\\(<,\infty )&(\leq ,0)\end{array}}\right)$ . Det representerar begränsningarna $0\leq 0+0$ , $x_{1}\leq 0+\infty$ , $0\leq x_{ 1}+\infty$ och $0\leq 0+0$ . Alla dessa begränsningar är uppfyllda oberoende av värdet som tilldelats $x_{1}$ . I återstoden av diskussionen kommer vi inte explicit att beskriva begränsningar på grund av inmatningar av formen ( $\displaystyle (<,\infty )}$ , eftersom dessa begränsningar är systematiskt uppfyllda.

DBM $\left({\begin{array}{ll}(<,\infty )&(<,\ infty )\\(<,\infty )&(<,\infty )\end{array}}\right)$ kodar också uppsättningen av real. Den innehåller begränsningarna $0<0+\infty$ och $x_{1}<x_{1}+\infty$ som är uppfyllda oberoende av värdet på $x_{1}$ . Detta visar att i en kanonisk DBM $D$ är en diagonal post aldrig större än $(\leq ,0)$ , eftersom matrisen som erhålls från $D$ genom att ersätta diagonal inmatning av $(\leq ,0)$ definierar samma uppsättning och är mindre än $D$ .

Den tomma uppsättningen

Vi betraktar nu många matriser som alla kodar den tomma mängden. Vi ger först den kanoniska DBM för den tomma uppsättningen. Vi förklarar sedan varför var och en av DBM kodar den tomma uppsättningen. Detta gör det möjligt att hitta begränsningar som måste uppfyllas av alla DBM.

Den kanoniska DBM för den tomma mängden, över en variabel, är $\left({\begin{array }{ll}(<,-\infty )&(<,-\infty )\\(<,-\infty )&(<,-\infty )\end{array}}\right)$ . Det representerar faktiskt uppsättningen som uppfyller villkoret $0<0-\infty$ , $0<x_{1}-\infty$ , $x_{1}<0-\infty$ och $x_{1}<x_{1}-\infty$ . Dessa begränsningar är otillfredsställande.

DBM $\left({\begin{array}{ll}(<,\infty )&(<, -\infty )\\(<,\infty )&(<,\infty )\end{array}}\right)$ kodar också den tomma uppsättningen. Den innehåller faktiskt begränsningen $x_{1}<0-\infty$ som är otillfredsställande. Mer generellt visar detta att ingen post kan vara $(<,-\infty )$ om inte alla poster är $(<,-\infty )$ .

DBM $\left({\begin{array}{ll}(<,\infty )&(<, \infty )\\(<,\infty )&(<,-1)\end{array}}\right)$ kodar också den tomma uppsättningen. Den innehåller faktiskt begränsningen $x_{1}<x_{1}-1$ som är otillfredsställande. Mer generellt visar detta att inmatningen i den diagonala linjen inte kan vara mindre än $(\leq ,0)$ om det inte är $(<,-\infty )$ .

DBM $\left({\begin{array}{ll}(<,\infty )&(<, 1)\\(\leq ,-1)&(<,\infty )\end{array}}\right)$ kodar också den tomma uppsättningen. Den innehåller faktiskt begränsningarna $0<x_{1}+1$ och $x_{1}\leq -1$ som är motsägelsefulla. Mer generellt visar detta att för varje $C,R\in \{0,x_{1},\dots ,x_{n}\}$ , om $m_{C,R}=-m_{R,C}$ , då $\prec _{R,C}$ och $\prec _{C,R}$ är båda lika med ≤.

DBM $\left({\begin{array}{ll}(<,\infty )&(\leq ,1)\\(\leq ,-2)&(<,\infty )\end{array}}\right)$ kodar också den tomma uppsättningen. Den innehåller faktiskt begränsningarna $0\leq x_{1}+1$ och $x_{1}\leq -2$ som är motsägelsefulla. Mer generellt visar detta att för varje $C,R\in \{0,x_{1},\dots ,x_{n}\}$ , ${\displaystyle -m_{C,R}\leq m_{R,C}} ,$ om inte $m_{C,R}$ är ${\ displaystyle -\infty }$ .

Strikta begränsningar

Exemplen som ges i det här avsnittet liknar exemplen som ges i exempelavsnittet ovan. Den här gången ges de som DBM.

DBM ${\ vänster({\begin{array}{lll}(\leq ,0)&(<,\infty )&(<,\infty )\\(<,\infty )&(\leq ,0)&(\leq ,3)\\(\leq ,3)&(<,\infty )&(\leq ,0)\end{array}}\right)} representerar uppsättningen som uppfyller begränsningarna x 2 ≤$ 3 ${ 2}\leq 3}$ och $x_{1}\leq x_{2}+3$ . Som nämnts i exempelavsnittet innebär båda dessa begränsningar att $x_{1}\leq 6$ . $\displaystyle \left({\begin{array}{lll}(\leq ,0)&(\leq ,6)&(<,\infty )\\(<,\infty )&(\leq ,0)& (\leq ,3)\\(\leq ,3)&(<,\infty )&(\leq ,0)\end{array}}\right)} kodar samma zon$$betyder$ att DBM . Egentligen är det DBM för denna zon. Detta visar att i vilken DBM som helst ${\displaystyle ((\prec _{C,R},m_{C ,R}))_{c,r\in \{0,x_{1},\dots ,x_{n}\}}} , för varje 1 ≤ i , j ≤$ n $, j\leq n}$ , begränsningen ${\displaystyle (\prec _{x_{i},0},m_{x_{i},0})} är$ mindre än begränsning $(\prec _{x_{j},0},m_{x_{j} ,0})+(\prec _{x_{i},x_{j}},m_{x_{i},x_{j}})$ .

Som förklarats i exempelavsnittet kan konstanten 0 betraktas som vilken variabel som helst, vilket leder till den mer allmänna regeln: i alla DBM $((\prec _{C,R},m_{C,R}))_{c,r\in \{0,x_{1},\dots ,x_{n} \}}$ , för varje $a,b,c\in \{0,x_{1},\dots ,x_{n}\ }$ , begränsningen $(\prec _{a,b},m_{a,b})$ är mindre än begränsningen $(\prec _{c,b},m_{c,b})+(\prec _{a,c},m_{a, c})$ .

Tre definitioner av kanonisk DBM

Som förklaras i inledningen av avsnittet Difference Bound Matrix , är en kanonisk DBM en DBM vars rader och kolumner är indexerade med $(0,x_{1},\dots ,x_ {n})$ , vars poster är begränsningar. Dessutom följer den en av följande likvärdiga egenskaper.

• det finns inga mindre DBM som definierar samma zon,
• för varje ${\displaystyle a,b,c\in \{0,x_{1},\dots ,x_{n}\}},$ begränsningen $(\prec _{a,b},m_{a,b})$ är mindre än begränsningen $(\prec _{c,b},m_{c,b})+(\prec _{a,c},m_{a,c})$
• givet den riktade grafen $G$ med kanter $\{0,x_{1},\dots ,x_{n}\}$ och pilar $(a,b)$ märkt av $(\prec _{a,b},m_{a,b})$ , den kortaste vägen från någon kant $a$ till valfri kant $b$ är pilen $(a,b)$ . Denna graf kallas potentialgrafen för DBM.

Den sista definitionen kan användas direkt för att beräkna den kanoniska DBM som är kopplad till en DBM. Det räcker att tillämpa Floyd–Warshall-algoritmen på grafen och associerar till varje post $(a,b)$ den kortaste vägen från $a$ till $b$ i Graf. Om denna algoritm upptäcker en cykel med negativ längd, betyder detta att begränsningarna inte är tillfredsställande, och därmed att zonen är tom.

Verksamhet på zoner

Som nämnts i inledningen är det huvudsakliga intresset för DBM:er att de gör det möjligt att enkelt och effektivt implementera operationer på zoner.

Vi minns först operationer som övervägdes ovan:

• testning för inkludering av en zon $Z_{1}$ i en zon $Z_{2}$ görs genom att testa om den kanoniska DBM för $Z_{1}$ är mindre än eller lika med DBM för $Z_{2}$ ,
• En DBM för skärningspunkten mellan en uppsättning zoner är den största-nedre gränsen för DBM för dessa zoner,
• testning av zontomhet består i att kontrollera om zonens kanoniska DBM endast består av $(<,-\infty )$ ,
• att testa om en zon är hela utrymmet består i att kontrollera om zonens DBM endast består av $(<,\infty )$ .

Vi beskriver nu operationer som inte beaktades ovan. De första operationerna som beskrivs nedan har tydlig geometrisk betydelse. De sista blir motsvarar operationer som är mer naturliga för klockvärderingar .

Summan av zoner

Minkowskisumman av två zoner, definierade av två DBMs $D$ och $D'$ , definieras av DBM $D+D'$ vars $(a,b)$ posten är $D_{a,b}+D'_{a,b}$ . Observera att eftersom $+$ är «produkten»-operationen av semiring av begränsningar, är operationen $+$ över DBM:er faktiskt inte en operation av modulen för DBM.

I synnerhet följer det att, för att översätta en zon $Z$ med en riktning $v$ , räcker det att lägga till DBM för $\{v\}$ till DBM för $Z$ .

Projektion av en komponent till ett fast värde

Låt $d\in M$ en konstant.

Givet en vektor ${\vec {x}}=(x_{1},\dots ,x_{n})$ och ett index $1\leq i\leq n$ , projektionen av $i$ -:e komponenten av ${\vec {x}}$ till $d$ är vektorn $(x_{1},\dots ,x_{i-1},d,x_{i+1}, \dots ,x_{n})$ . På klockspråket, för $d=0$ , motsvarar detta att återställa den $i$ -th klockan.

Att projicera den $i$ -te komponenten i en zon $Z$ till $d$ består helt enkelt av uppsättningen vektorer av $Z$ med deras $i$ - komponenten till $d$ . Detta implementeras $(\leq ,d)+D (0,a)$ DBM genom att ställa in komponenterna $(x_{i},a)}$ till och komponenterna $(a,x_{i})$ till $(\leq ,-d) +D(0,a)$

Framtid och dåtid för en zon

Låt oss kalla framtiden för zonen $F=\{(t,\dots ,t)\mid t\in \mathbb {R} _{ \geq 0}\}$ och det förflutna zonen $P=\{(-t,\dots ,-t)\mid t \in \mathbb {R} _{\geq 0}\}$ . Givet en punkt ${\vec {x}}=(x_{1},\dots ,x_{n})\in \mathbb {R} ^{n}$ , framtiden för ${\vec {x}}$ definieras som $\{(x_{1}+t,\dots ,x_{n}+t)\mid t\in \mathbb {R} _{\geq 0}\}=F+\{{\vec {x}}\}$ och det förflutna för ${\vec {x}}$ definieras som $P+\{{\vec {x}}\}$ .

Namnen framtid och förflutet kommer från begreppet klocka . Om en uppsättning av $n$ klockor tilldelas värdena $x_{1}$ , $x_{2}$ , etc. så kommer tilldelningsuppsättningen i framtiden att de kommer att ha är framtiden för ${\vec {x}}$ .

Givet en zon ${\displaystyle Z} är$ framtiden för $Z$ föreningen av framtiden för varje punkt i zonen. Definitionen av det förflutna av en zon är liknande. Framtiden för en zon kan alltså definieras som $F+Z$ , och kan därför enkelt implementeras som en summa av DBM. Det finns dock ännu en enklare algoritm att tillämpa på DBM. Det räcker med att ändra varje post $(x_{i},0)$ till $(<,\infty )$ . På liknande sätt kan $) {\displaystyle (<,\infty )}$ förflutna för en zon beräknas genom att ställa in alla poster $(0,x_{i})$ till .

Se även

• Region (modellkontroll) – en zon, minimal under inkludering, som uppfyller vissa egenskaper

• Difference Bound Matrices Föreläsning #20 av Advanced Model Checking Joost-Pieter Katoen
•   Péron, Mathias; Halbwachs, Nicolas (2008). "En abstrakt domän som utökar skillnadsbundna matriser med ojämlikhetsbegränsningar" ( PDF) . Föreläsningsanteckningar i datavetenskap . 4349 : 268–282. doi : 10.1007/978-3-540-69738-1_20 . ISBN 978-3-540-69735-0 .