Rozdílem vázaná matice - Difference bound matrix

v kontrola modelu, pole počítačová věda, a rozdílová vázaná matice (DBM) je datová struktura představovaly nějaké konvexní polytopes volala zóny. Tuto strukturu lze použít k efektivní implementaci některých geometrických operací nad zónami, jako je testování prázdnoty, začlenění, rovnosti a výpočet průsečíku a součtu dvou zón. Používá se například v Uppaal model checker; kde je také distribuován jako samostatná knihovna.^[1]

Přesněji řečeno, existuje pojem kanonického DBM; mezi kanonickými DBM a zónami existuje vztah jedna k jedné a z každého DBM lze efektivně vypočítat kanonický ekvivalent DBM. Rovnost zóny lze tedy otestovat kontrolou rovnosti kanonických DBM.

Zóna

Rozdílně vázaná matice se používá k reprezentaci určitého druhu konvexních polytopů. Tito polytopy se nazývají zóna. Nyní jsou definovány. Formálně je zóna definována rovnicemi formy ${ displaystyle x leq c}$, ${ displaystyle x geq c}$, ${ displaystyle x_ {1} leq x_ {2} + c}$ a ${ displaystyle x_ {1} geq x_ {2} + c}$, s ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$ některé proměnné a ${ displaystyle c}$ konstanta.

Zóny byly původně nazývány kraj,^[2] ale dnes toto jméno obvykle označuje kraj, zvláštní druh zóny. Intuitivně, a kraj lze považovat za minimální neprázdné zóny, ve kterých jsou omezeny konstanty použité v omezení.

Dáno ${ displaystyle n}$ proměnné, existují přesně ${ displaystyle n (n + 1)}$ jsou možná různá neredundantní omezení, ${ displaystyle n}$ omezení, která používají jedinou proměnnou a horní mez, ${ displaystyle n}$ omezení, která používají jednu proměnnou a dolní mez, a pro každou z ${ displaystyle n ^ {2}}$ seřazené páry proměnných ${ displaystyle (x, y)}$, horní mez na ${ displaystyle x-y}$. Nicméně svévolné konvexní mnohostěn v ${ displaystyle mathbb {R} ^ {n}}$ může vyžadovat libovolně velké množství omezení. I když ${ displaystyle n = 2}$, může existovat libovolné velké množství neredundantních omezení ${ displaystyle (x$, pro ${ displaystyle c_ {i}}$ některé konstanty. To je důvod, proč nelze DBM rozšířit ze zón na konvexní polytopy.

Příklad

Jak je uvedeno v úvodu, uvažujeme o zóně definované sadou příkazů formuláře ${ displaystyle x_ {1} leq c}$, ${ displaystyle x_ {1} geq c}$, ${ displaystyle x_ {1} leq x_ {2} + c}$ a ${ displaystyle x_ {1} geq x_ {2} + c}$, s ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$ některé proměnné a ${ displaystyle c}$ konstanta. Některá z těchto omezení jsou však buď rozporuplná, nebo nadbytečná. Nyní uvádíme takové příklady.

• omezení ${ displaystyle x_ {1} leq 3}$ a ${ displaystyle x_ {1} geq 4}$ jsou rozporuplné. Když jsou tedy nalezena dvě taková omezení, definovaná zóna je prázdná.
  

  Postavte se ${ textstyle mathbb {R} ^ {2}}$ zobrazeno ${ textstyle x_ {1} leq 3}$, ${ textstyle x_ {1} geq 4}$ které jsou disjunktní
• omezení ${ displaystyle x_ {1} leq 3}$ a ${ displaystyle x_ {1} leq 4}$ jsou nadbytečné. Druhé omezení implikované prvním. Pokud se tedy v definici zóny nacházejí dvě taková omezení, může být druhé omezení odstraněno.
  

  Postavte se ${ textstyle mathbb {R} ^ {2}}$ zobrazeno ${ textstyle x_ {1} leq 3}$ a ${ textstyle x_ {1} leq 4}$ který obsahuje první obrázek

Uvádíme také příklad, jak generovat nová omezení z existujících omezení. Pro každý pár hodin ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$, má DBM omezení formuláře ${ displaystyle x_ {1} prec x_ {2} + c}$, kde ${ displaystyle prec}$ je buď ${ displaystyle x_ {1} prec x_ {2} + infty}$ lze přidat k definici zóny bez ztráty obecnosti. V některých případech však lze nalézt přesnější omezení. Nyní bude uveden takový příklad.

• omezení ${ displaystyle x_ {1} leq 3}$, ${ displaystyle x_ {2} geq -3}$ to naznačuje ${ displaystyle x_ {1} leq x_ {2} +6}$. Tedy za předpokladu, že žádná jiná omezení jako např ${ displaystyle x_ {1} leq x_ {2} +5}$ nebo ${ displaystyle x_ {1}$ patří k definici, omezení ${ displaystyle x_ {1} leq x_ {2} +6}$ je přidán k definici zóny.
  

  Postavte se ${ textstyle mathbb {R} ^ {2}}$ zobrazeno ${ textstyle x_ {1} leq 3}$, ${ textstyle x_ {2} geq -3}$ a jejich křižovatky
• omezení ${ displaystyle x_ {2} leq 3}$, ${ displaystyle x_ {1} leq x_ {2} +3}$ to naznačuje ${ displaystyle x_ {1} leq 6}$. Tedy za předpokladu, že žádná jiná omezení jako např ${ displaystyle x_ {1} leq 5}$ nebo ${ displaystyle x_ {1} <6}$ patří k definici, omezení ${ displaystyle x_ {1} leq 6}$ je přidán k definici zóny.
  

  Postavte se ${ textstyle mathbb {R} ^ {2}}$ zobrazeno ${ textstyle x_ {1} leq 3}$, ${ textstyle x_ {1} leq x_ {2} +3}$ a jejich křižovatky
• omezení ${ displaystyle x_ {1} leq x_ {2} +3}$, ${ displaystyle x_ {2} leq x_ {3} +3}$ to naznačuje ${ displaystyle x_ {1} leq x_ {3} +6}$. Tedy za předpokladu, že žádná jiná omezení jako např ${ displaystyle x_ {1} leq x_ {3} +5}$ nebo ${ displaystyle x_ {1}$ patří k definici, omezení ${ displaystyle x_ {1} leq x_ {3} +6}$ je přidán k definici zóny.

Ve skutečnosti jsou první dva výše uvedené případy konkrétními případy třetích případů. Vskutku, ${ displaystyle x_ {1} leq 3}$ a ${ displaystyle x_ {2} geq -3}$ lze přepsat jako ${ displaystyle x_ {1} leq 0 + 3}$ a ${ displaystyle 0 leq x_ {2} +3}$ resp. A tedy omezení ${ displaystyle x_ {1} leq x_ {2} +6}$ added in the first example is similar to the constraint added in the third example.

Definice

Nyní opravíme a monoidní ${ displaystyle (M, 0, +)}$ což je podmnožina skutečné linie. Tento monoid je tradičně soubor celá čísla, racionální, realita nebo jejich podmnožina nezáporných čísel.

Omezení

Za účelem definování datové struktury rozdílová vázaná matice, je nejprve nutné dát datovou strukturu pro kódování atomových omezení. Dále zavedeme algebru pro atomová omezení. Tato algebra je obdobou tropický semiring, se dvěma úpravami:

• Namísto ℝ lze použít libovolný seřazený monoid.
• Aby bylo možné rozlišovat mezi „${ displaystyle$" a "${ displaystyle leq m}$", sada prvků algebry musí obsahovat informace o tom, zda je pořadí přísné nebo ne.

Definice omezení

Sada uspokojivá omezení je definována jako sada dvojic formuláře:

• ${ displaystyle ( leq, m)}$, s ${ displaystyle m v M}$, což představuje omezení formuláře ${ displaystyle leq m}$,
• ${ displaystyle (<, m)}$, s ${ displaystyle m v M}$, kde ${ displaystyle m}$ není minimálním prvkem ${ displaystyle M}$, což představuje omezení formuláře ${ displaystyle$,
• ${ displaystyle (<, infty)}$, což představuje absenci omezení.

Sada omezení obsahuje všechna uspokojivá omezení a obsahuje také následující nevyhovující omezení:

• ${ displaystyle (<, - infty)}$.

Podmnožina ${ displaystyle {q v mathbb {Q} střední q leq { sqrt {2}} }}$ nelze definovat pomocí tohoto druhu omezení. Obecněji, některé konvexní polytopy nelze definovat, když uspořádaný monoid nemá vlastnost s nejmenší horní hranicí, i když každé z omezení ve své definici používá nejvýše dvě proměnné.

Provoz na omezeních

Abychom vygenerovali jediné omezení z dvojice omezení aplikovaných na stejnou (dvojici) proměnné, formalizujeme pojem průnik omezení a pořadí nad omezeními. Podobně, aby bylo možné definovat nová omezení z existujících omezení, musí být také definován pojem součet omezení.

Objednávka na omezení

Nyní definujeme relační řád přes omezení. Toto pořadí symbolizuje relaci začlenění.

Nejprve sada ${ displaystyle {<, leq }}$ je považována za uspořádanou množinu, přičemž ${ displaystyle x$ je striktně zahrnut v sadě definované ${ displaystyle x leq c}$. Poté uvedeme toto omezení ${ displaystyle ( prec _ {1}, m_ {1})}$ je menší než ${ displaystyle ( prec _ {2}, m_ {2})}$ pokud ano ${ displaystyle m_ {1}$ nebo (${ displaystyle m_ {1} = m_ {2}}$ a ${ displaystyle prec _ {1}}$ je méně než ${ displaystyle prec _ {2}}$). To znamená, že pořadí omezení je lexikografický řád aplikováno zprava doleva. Tato objednávka je a celková objednávka. Li ${ displaystyle M}$ má vlastnost s nejmenší horní hranicí (nebo vlastnost s nejvyšší vazbou ), pak jej má také sada omezení.

Křižovatka omezení

Průsečík dvou omezení, označených jako ${ displaystyle ( prec _ {1}, m_ {1}) sqcap ( prec _ {2}, m_ {2})}$, je pak jednoduše definováno jako minimum z těchto dvou omezení. Li ${ displaystyle M}$ má vlastnost největší-dolní hranice, pak je také definován průnik nekonečného počtu omezení.

Součet omezení

Vzhledem k tomu, dvě proměnné ${ displaystyle x_ {1}}$ a ${ displaystyle x_ {2}}$ na které se vztahují omezení ${ displaystyle ( prec _ {1}, m_ {1})}$ a ${ displaystyle ( prec _ {2}, m_ {2})}$, nyní vysvětlíme, jak vygenerovat omezení spokojené s ${ displaystyle x_ {1} + x_ {2}}$. Toto omezení se nazývá součet dvou výše uvedených omezení, označuje se jako ${ displaystyle ( prec _ {1}, m_ {1}) + ( prec _ {2}, m_ {2})}$ a je definován jako ${ displaystyle ( min ( prec _ {1}, prec _ {2}), m_ {1} + m_ {2})}$.

Omezení jako algebra

Zde je seznam algebraických vlastností splněných množinou omezení.

• Obě operace jsou asociativní a komutativní,
• Součet je distribuční přes křižovatku, to znamená pro všechna tři omezení, ${ displaystyle (( prec _ {1}, m_ {1}) sqcap ( prec _ {2}, m_ {2})) + ( prec _ {3}, m_ {3})}$ rovná se ${ displaystyle (( prec _ {1}, m_ {1}) + ( prec _ {3}, m_ {3})) sqcap (( prec _ {2}, m_ {2}) + ( prec _ {3}, m_ {3}))}$,
• Průnik je idempotentní,
• Omezení ${ displaystyle (<, infty)}$ je identita operace křižovatky,
• Omezení ${ displaystyle ( leq, 0)}$ je identita operace součtu,

Následující algebraické vlastnosti dále platí nad uspokojivými omezeními:

• Omezení ${ displaystyle (<, infty)}$ je nula pro operaci součtu,
• Z toho vyplývá, že množina uspokojivých omezení je idempotentní semiring, s ${ displaystyle (<, infty)}$ jako nula a ${ displaystyle ( leq, 0)}$ jako jednota.
• Pokud 0 je minimální prvek ${ displaystyle M}$, pak ${ displaystyle ( leq, 0)}$ je nula pro omezení průsečíku přes uspokojivá omezení.

Přes nevyhovující omezení mají obě operace stejnou nulu, což je ${ displaystyle (<, - infty)}$. Sada omezení tedy netvoří ani semiring, protože identita křižovatky je odlišná od nuly součtu.

DBM

Vzhledem k souboru ${ displaystyle n}$ proměnné, ${ displaystyle x_ {1}, tečky, x_ {n}}$, DBM je matice se sloupci a řádky indexovanými podle ${ displaystyle 0, x_ {1}, tečky, x_ {n}}$ a položky jsou omezení. Intuitivně pro sloup ${ displaystyle C}$ a řádek ${ displaystyle R}$, hodnota ${ displaystyle m}$ v poloze ${ displaystyle (C, R)}$ představuje ${ displaystyle C prec R + m}$. To znamená, že zóna definovaná maticí ${ displaystyle D (( prec _ {C, R}, m_ {C, R})) _ {C, R v {0, x_ {1}, tečky, x_ {n}} }}$, označeno ${ displaystyle { mathcal {R}} (D)}$, je ${ displaystyle {(x_ {1}, tečky, x_ {n}) in mathbb {R} mid bigwedge _ {C, R in {0, x_ {1}, dots, x_ {n} }} C prec _ {C, R} R + m_ {C, R} }}$.

Všimněte si, že ${ displaystyle C prec R + m}$ je ekvivalentní k ${ displaystyle C-R prec m}$, tedy záznam ${ displaystyle ( prec, m)}$ je stále v podstatě horní mez. Všimněte si však, že jelikož považujeme monoid ${ displaystyle M}$, pro některé hodnoty ${ displaystyle C}$ a ${ displaystyle R}$ skutečný ${ displaystyle C-R}$ ve skutečnosti nepatří k monoidovi.

Před zavedením definice kanonického DBM musíme na těchto maticích definovat a prodiskutovat vztah objednávek.

Objednávka na těchto maticích

Matice ${ displaystyle D}$ je považován za menší než matice ${ displaystyle D '}$ pokud je každá z jejích položek menší. Tato objednávka není úplná. Vzhledem k tomu, dva DBM ${ displaystyle D}$ a ${ displaystyle D '}$, pokud ${ displaystyle D}$ je menší nebo rovno ${ displaystyle D '}$, pak ${ displaystyle { mathcal {R}} (D) subseteq { mathcal {R}} (D ')}$.

Největší dolní mez dvou matic ${ displaystyle D}$ a ${ displaystyle D '}$, označeno ${ displaystyle D sqcap D '}$, má jako svůj ${ displaystyle (a, b)}$ zadejte hodnotu ${ displaystyle ( prec _ {a, b}, m_ {a, b}) sqcap ( prec '_ {a, b}, m' _ {a, b})}$. Všimněte si, že od té doby ${ displaystyle sqcap}$ je operace „součtu“ semiring omezení, operace ${ displaystyle sqcap}$ je «součet» dvou DBM, kde je sada DBM považována za a modul.

Podobně jako v případě omezení, uvažovaných výše v části „Provoz s omezeními“, je nejvyšší-dolní hranice nekonečného počtu matic správně definována, jakmile ${ displaystyle M}$ splňuje vlastnost nejvyšší-dolní mez.

Je definován průnik matic / zón. Operace spojení není definována a spojení zóny není obecně zónou.

Pro libovolnou množinu ${ displaystyle { mathcal {D}}}$ matic, které všechny definují stejnou zónu ${ displaystyle Z}$, ${ displaystyle sqcap _ {D v { mathcal {D}}} D}$ také definuje ${ displaystyle Z}$. Z toho tedy vyplývá, pokud ${ displaystyle M}$ má vlastnost největší-dolní mez, každá zóna, která je definována alespoň maticí, má jedinečnou minimální matici, která ji definuje. Tato matice se nazývá kanonická DBM z ${ displaystyle Z}$.

První definice kanonického DBM

Přepracováváme definici a kanonický rozdíl vázaná matice. Jedná se o DBM, takže žádná menší matice nedefinuje stejnou sadu. Níže je vysvětleno, jak zkontrolovat, zda je matice DBM, a jak vypočítat DBM z libovolné matice tak, aby obě matice představovaly stejnou sadu. Nejprve ale uvedeme několik příkladů.

Příklady matic

Nejprve uvažujeme případ, kdy existují jediné hodiny ${ displaystyle x_ {1}}$.

Skutečná linie

Nejprve dáme kanonický DBM pro ${ displaystyle mathbb {R}}$. Poté představíme další DBM, který kóduje sadu ${ displaystyle mathbb {R}}$. To umožňuje najít omezení, která musí splňovat jakýkoli DBM.

Kanonický DBM množiny skutečných je ${ displaystyle left ({ begin {pole} {ll} ( leq, 0) & (<, infty) (<, infty) & ( leq, 0) end {pole}} že jo)}$. Představuje omezení ${ displaystyle 0 leq 0 + 0}$, ${ displaystyle x_ {1} leq 0+ infty}$, ${ displaystyle 0 leq x_ {1} + infty}$ a ${ displaystyle 0 leq 0 + 0}$. Všechna tato omezení jsou splněna nezávisle na hodnotě přiřazené ${ displaystyle x_ {1}}$. Ve zbývající části diskuse nebudeme explicitně popisovat omezení způsobená vstupy do formuláře ${ displaystyle (<, infty)}$, protože tato omezení jsou systematicky uspokojována.

DBM ${ displaystyle left ({ begin {pole} {ll} (<, infty) & (<, infty) (<, infty) & (<, infty) end {pole}} že jo)}$ také kóduje množinu skutečných. Obsahuje omezení ${ displaystyle 0 <0+ infty}$ a ${ displaystyle x_ {1}$ které jsou uspokojeny nezávisle na hodnotě ${ displaystyle x_ {1}}$. To ukazuje, že v kanonickém DBM ${ displaystyle D}$, úhlopříčný záznam nikdy není větší než ${ displaystyle ( leq, 0)}$, protože matice získaná z ${ displaystyle D}$ nahrazením diagonálního vstupu znakem ${ displaystyle ( leq, 0)}$ definuje stejnou sadu a je menší než ${ displaystyle D}$.

Prázdná sada

Nyní uvažujeme mnoho matic, které všechny kódují prázdnou sadu. Nejprve dáme kanonický DBM pro prázdnou množinu. Poté vysvětlíme, proč každý z DBM kóduje prázdnou množinu. To umožňuje najít omezení, která musí splňovat jakýkoli DBM.

Kanonický DBM prázdné množiny přes jednu proměnnou je ${ displaystyle left ({ begin {pole} {ll} (<, - infty) & (<, - infty) (<, - infty) & (<, - infty) end { pole}} vpravo)}$. Ve skutečnosti představuje množinu splňující omezení ${ displaystyle 0 <0- infty}$, ${ displaystyle 0$, ${ displaystyle x_ {1} <0- infty}$ a ${ displaystyle x_ {1}$. Tato omezení jsou neuspokojitelná.

DBM ${ displaystyle left ({ begin {pole} {ll} (<, infty) & (<, - infty) (<, infty) & (<, infty) end {pole}} že jo)}$ také kóduje prázdnou sadu. Ve skutečnosti obsahuje omezení ${ displaystyle x_ {1} <0- infty}$ což je neuspokojitelné. Obecněji to ukazuje, že žádný záznam nemůže být ${ displaystyle (<, - infty)}$ pokud nejsou všechny položky ${ displaystyle (<, - infty)}$.

DBM ${ displaystyle left ({ begin {pole} {ll} (<, infty) & (<, infty) (<, infty) & (<, - 1) end {pole}} že jo)}$ také kóduje prázdnou sadu. Ve skutečnosti obsahuje omezení ${ displaystyle x_ {1}$ což je neuspokojivé. Obecněji to ukazuje, že položka v diagonální linii nemůže být menší než ${ displaystyle ( leq, 0)}$ pokud není ${ displaystyle (<, - infty)}$.

DBM ${ displaystyle left ({ begin {pole} {ll} (<, infty) & (<, 1) ( leq, -1) & (<, infty) end {pole}} že jo)}$ také kóduje prázdnou sadu. Ve skutečnosti obsahuje omezení ${ displaystyle 0$ a ${ displaystyle x_ {1} leq -1}$ které si odporují. Obecněji to ukazuje, že pro každého ${ displaystyle C, R v {0, x_ {1}, tečky, x_ {n} }}$, pokud ${ displaystyle m_ {C, R} = - m_ {R, C}}$, pak ${ displaystyle prec _ {R, C}}$ a ${ displaystyle prec _ {C, R}}$ jsou obě rovny ≤.

DBM ${ displaystyle left ({ begin {pole} {ll} (<, infty) & ( leq, 1) ( leq, -2) & (<, infty) end {pole}} že jo)}$ také kóduje prázdnou sadu. Ve skutečnosti obsahuje omezení ${ displaystyle 0 leq x_ {1} +1}$ a ${ displaystyle x_ {1} leq -2}$ které si odporují. Obecněji to ukazuje, že pro každého ${ displaystyle C, R v {0, x_ {1}, tečky, x_ {n} }}$, ${ displaystyle -m_ {C, R} leq m_ {R, C}}$, pokud ${ displaystyle m_ {C, R}}$ je ${ displaystyle - infty}$.

Přísná omezení

Příklady uvedené v této části jsou podobné příkladům uvedeným v části Příklad výše. Tentokrát jsou uvedeny jako DBM.

DBM ${ displaystyle left ({ begin {pole} {lll} ( leq, 0) & (<, infty) & (<, infty) (<, infty) & ( leq, 0) & ( leq, 3) ( leq, 3) & (<, infty) & ( leq, 0) end {array}} right)}$ představuje množinu splňující omezení ${ displaystyle x_ {2} leq 3}$ a ${ displaystyle x_ {1} leq x_ {2} +3}$. Jak je uvedeno v části Příklad, obě tato omezení to implikují ${ displaystyle x_ {1} leq 6}$. To znamená, že DBM ${ displaystyle left ({ begin {pole} {lll} ( leq, 0) & ( leq, 6) & (<, infty) (<, infty) & ( leq, 0) & ( leq, 3) ( leq, 3) & (<, infty) & ( leq, 0) end {array}} right)}$ kóduje stejnou zónu. Ve skutečnosti je to DBM této zóny. To ukazuje, že v každém DBM ${ displaystyle (( prec _ {C, R}, m_ {C, R})) _ {c, r in {0, x_ {1}, dots, x_ {n} }}}$, pro každého ${ displaystyle 1 leq i, j leq n}$omezení ${ displaystyle ( prec _ {x_ {i}, 0}, m_ {x_ {i}, 0})}$ je menší než omezení ${ displaystyle ( prec _ {x_ {j}, 0}, m_ {x_ {j}, 0}) + ( prec _ {x_ {i}, x_ {j}}, m_ {x_ {i}, x_ {j}})}$.

Jak je vysvětleno v části Příklad, konstantu 0 lze považovat za libovolnou proměnnou, což vede k obecnějšímu pravidlu: v libovolném DBM ${ displaystyle (( prec _ {C, R}, m_ {C, R})) _ {c, r in {0, x_ {1}, dots, x_ {n} }}}$, pro každého ${ displaystyle a, b, c v {0, x_ {1}, tečky, x_ {n} }}$omezení ${ displaystyle ( prec _ {a, b}, m_ {a, b})}$ je menší než omezení ${ displaystyle ( prec _ {c, b}, m_ {c, b}) + ( prec _ {a, c}, m_ {a, c})}$.

Tři definice kanonického DBM

Jak je vysvětleno v úvodu této části Rozdíl vázané matice, kanonický DBM je DBM, jehož řádky a sloupce jsou indexovány pomocí ${ displaystyle (0, x_ {1}, tečky, x_ {n})}$, jejichž položky jsou omezeními. Dále sleduje jednu z následujících ekvivalentních vlastností.

• neexistují žádné menší DBM definující stejnou zónu,
• pro každého ${ displaystyle a, b, c v {0, x_ {1}, tečky, x_ {n} }}$omezení ${ displaystyle ( prec _ {a, b}, m_ {a, b})}$ je menší než omezení ${ displaystyle ( prec _ {c, b}, m_ {c, b}) + ( prec _ {a, c}, m_ {a, c})}$
• vzhledem k řízený graf ${ displaystyle G}$ s hranami ${ displaystyle {0, x_ {1}, tečky, x_ {n} }}$ a šipky ${ displaystyle (a, b)}$ označeno ${ displaystyle ( prec _ {a, b}, m_ {a, b})}$, nejkratší cesta od kteréhokoli okraje ${ displaystyle a}$ k jakémukoli okraji ${ displaystyle b}$ je šipka ${ displaystyle (a, b)}$. Tento graf se nazývá potenciální graf DBM.

Poslední definici lze přímo použít k výpočtu kanonického DBM přidruženého k DBM. Postačí použít Floyd-Warshallův algoritmus ke grafu a přidruží se ke každé položce ${ displaystyle (a, b)}$ nejkratší cesta z ${ displaystyle a}$ na ${ displaystyle b}$ v grafu. Pokud tento algoritmus detekuje cyklus záporné délky, znamená to, že omezení nejsou uspokojivá, a tedy že zóna je prázdná.

Operace v zónách

Jak bylo uvedeno v úvodu, hlavním zájmem DBM je, že umožňují snadno a efektivně provádět operace v zónách.

Nejprve si vzpomínáme na operace, které byly zvažovány výše:

• testování na zahrnutí zóny ${ displaystyle Z_ {1}}$ v zóně ${ displaystyle Z_ {2}}$ se provádí testováním, zda kanonický DBM z ${ displaystyle Z_ {1}}$ je menší nebo rovno kanonickému BDM z ${ displaystyle Z_ {2}}$,
• DBM pro průnik sady zón je největší-dolní mez DBM těchto zón,
• testování prázdnoty zóny spočívá v kontrole, zda kanonický DBM zóny sestává pouze z ${ displaystyle (<, - infty)}$,
• testování, zda je zóna celým prostorem, spočívá v kontrole, zda se DBM zóny skládá pouze z ${ displaystyle (<, infty)}$.

Nyní popíšeme operace, které nebyly uvažovány výše. První níže popsané operace mají jasný geometrický význam. Poslední z nich odpovídají operacím, které jsou pro ně přirozenější hodiny ocenění.

Součet zón

The Minkowského součet dvou zón, definovaných dvěma DBM ${ displaystyle D}$ a ${ displaystyle D '}$, je definován DBM ${ displaystyle D + D '}$ jehož ${ displaystyle (a, b)}$ položka je ${ displaystyle D_ {a, b} + D '_ {a, b}}$. Všimněte si, že od té doby ${ displaystyle +}$ je operace «produktu» semiring omezení, operace ${ displaystyle +}$ přes DBM není ve skutečnosti operací modul DBM.

Z toho zejména vyplývá, že za účelem překladu zóny ${ displaystyle Z}$ směrem ${ displaystyle v}$, stačí přidat DBM z ${ displaystyle {v }}$ do DBM z ${ displaystyle Z}$.

Projekce komponenty na pevnou hodnotu

Nechat ${ displaystyle d v M}$ konstanta.

Vzhledem k vektoru ${ displaystyle { vec {x}} = (x_ {1}, tečky, x_ {n})}$a index ${ Displaystyle 1 leq i leq n}$, projekce ${ displaystyle i}$-tá složka ${ displaystyle { vec {x}}}$ na ${ displaystyle d}$ je vektor ${ displaystyle (x_ {1}, tečky, x_ {i-1}, d, x_ {i + 1}, tečky, x_ {n})}$. V jazyce hodin, pro ${ displaystyle d = 0}$, to odpovídá resetování ${ displaystyle i}$-th hodiny.

Promítání ${ displaystyle i}$-tá složka zóny ${ displaystyle Z}$ na ${ displaystyle d}$ spočívá jednoduše v sadě vektorů ${ displaystyle Z}$ s jejich ${ displaystyle i}$-tá složka ${ displaystyle d}$. To je implementováno na DBM nastavením komponent ${ displaystyle (x_ {i}, a)}$ na ${ displaystyle ( leq, d) + D (0, a)}$ a komponenty ${ displaystyle (a, x_ {i})}$ na ${ displaystyle ( leq, -d) + D (0, a)}$

Budoucnost a minulost zóny

Zavolejme budoucnost zóna ${ displaystyle F = {(t, tečky, t) střední t v mathbb {R} _ { geq 0} }}$ a minulost zóna ${ displaystyle P = {(- t, tečky, -t) střední t v mathbb {R} _ { geq 0} }}$. Daný bod ${ displaystyle { vec {x}} = (x_ {1}, tečky, x_ {n}) v mathbb {R} ^ {n}}$, budoucnost ${ displaystyle { vec {x}}}$ je definován jako ${ displaystyle {(x_ {1} + t, tečky, x_ {n} + t) mid t in mathbb {R} _ { geq 0} } = F + {{ vec {x }} }}$a minulost ${ displaystyle { vec {x}}}$ je definován jako ${ displaystyle P + {{ vec {x}} }}$.

Názvy budoucnost a minulost vycházejí z pojmu hodiny. Pokud soubor ${ displaystyle n}$ hodinám jsou přiřazeny hodnoty ${ displaystyle x_ {1}}$, ${ displaystyle x_ {2}}$atd., pak v jejich budoucnosti bude soubor úkolů, které budou mít, budoucnost ${ displaystyle { vec {x}}}$.

Vzhledem k zóně ${ displaystyle Z}$, budoucnost ${ displaystyle Z}$ jsou spojením budoucnosti každého bodu zóny. Definice minulost zóny je podobný. Budoucnost zóny lze tedy definovat jako ${ displaystyle F + Z}$, a proto je lze snadno implementovat jako součet DBM. Pro DBM však existuje ještě jednodušší algoritmus. Postačí změnit každý záznam ${ displaystyle (x_ {i}, 0)}$ na ${ displaystyle (<, infty)}$. Podobně lze minulost zóny vypočítat nastavením všech položek ${ displaystyle (0, x_ {i})}$ na ${ displaystyle (<, infty)}$.

Viz také

• Region (kontrola modelu) - zóna, minimální zahrnutí, splňující některé vlastnosti

Reference

• Rozdíl vázaných matic Přednáška č. 20 Pokročilé kontroly modelu Joost-Pieter Katoen
• Péron, Mathias; Halbwachs, Nicolas (2008). „Abstraktní doména rozšiřující matice vázané na rozdíl s omezeními nerovnosti“ (PDF). Přednášky z informatiky. 4349: 268–282. doi:10.1007/978-3-540-69738-1_20. ISBN  978-3-540-69735-0.