Region (sprawdzanie modelu)

W sprawdzaniu modeli , dziedzinie informatyki , region jest wypukłym polytopem w pewnym wymiarze , a dokładniej strefą spełniającą pewne wymiary. ${\ displaystyle \ mathbb {R} ^ {d$$}$ właściwość minimalizmu. Podział regionów ${\ displaystyle \ mathbb {R} ^ {d}}$ .

Zbiór stref zależy od zestawu ograniczeń postaci $\$$Displaystyle x \ leq c}$ , $geq c}$ , ${\ Displaystyle x_ {1} \ równoważnik x_ {2} + c}$ i ${\ Displaystyle x_ {1} \ geq x_ {2} + c}$ z ${\ Displaystyle x_ {1 }}$ i $x_ {2}}$$displaystyle$ niektóre zmienne i . Regiony są zdefiniowane w taki sposób, że jeśli dwa wektory $vec {x}}}$ → { $\$ z ${\ displaystyle K}$ . Co więcej, gdy te wektory są traktowane jako krotka zegarów , oba wektory mają ten sam zestaw możliwych przyszłości. Intuicyjnie oznacza to, że każdy $formuła$ czasowych - lub automat czasowy lub automat sygnałowy używający tylko ograniczeń nie może rozróżnić obu wektorów.

Zbiór regionów pozwala na utworzenie automatu regionów , który jest grafem skierowanym , w którym każdy węzeł jest regionem, a każda krawędź zapewnia, że ${\ displaystyle r \ do r'}$${\ displaystyle r'}$ jest możliwą przyszłością ${\ displaystyle r}$ . $displaystyle$ iloczyn tego automatu regionu i automatu czasowego , który akceptuje język, tworzy ${\ mathcal {A}}}$ automat skończony lub automat Büchi $,$ który akceptuje nieokreślony . W szczególności pozwala zredukować problem pustki dla $.$ pustki dla automatu skończonego lub Büchi Technikę tę wykorzystuje np. oprogramowanie UPPAAL .

Definicja

Niech do $\ Displaystyle C = \ {x_ {1}, \ kropki, x_ {d} \}}$ zestaw zegarów . Dla każdego ${\ Displaystyle x \ in \ mathbb {N}}$ niech ${\ Displaystyle c_ {x} \ in \ mathbb {N}}$ . Intuicyjnie liczba ta reprezentuje górną granicę wartości, do których można porównać zegar ${\ displaystyle x} .$ Definicja regionu nad zegarami $}$ używa tych liczb ${\ displaystyle c_ {x}}$ 's. Podane są teraz trzy równoważne definicje.

$nu$ przypisanie zegara , $]}$$Displaystyle [\$ oznacza region, do którego . Zbiór regionów jest oznaczony przez ${\ displaystyle {\ mathcal {R}}}$ .

Równoważność przypisania zegarów

Pierwsza definicja pozwala w łatwy sposób sprawdzić, czy dwa przydziały należą do tego samego regionu.

Region można zdefiniować jako klasę równoważności dla pewnej relacji równoważności. Przypisania dwóch zegarów i są równoważne, jeśli spełniają następujące ograniczenia: ${\ displaystyle \ nu _ {1}}$ i ${\ displaystyle \ nu _ {2}}$

• ${\ Displaystyle \ nu _ {1} (x) \ sim c}$ iff ${\ Displaystyle \ nu _ {2} (x) \ sim c$ } ${\ Displaystyle x \ w C}$ ≤ $\ Displaystyle 0 \ równoważnik c \ równoważnik c_ {x}}$ liczba całkowita, a ~ jest jedną z następujących relacji = , < lub ≤ .
• ${\ Displaystyle \ {\ nu _ {1} (x) \} \ sim \ {\ nu _ {1} (y) \}}$ iff ${\ Displaystyle \ {\ nu _ {2} (x) \} \ sim \ {\ nu _ {2} (y) \}}$ dla każdego ${\ Displaystyle x, y \ w C}$ , ${\ Displaystyle \ nu _ {1} (x) \ równoważnik c_ {x}}$ , ${\ Displaystyle \ nu _ {1} (y) \ równoważnik c_ { y}}$ , $}$$}$ będąc ułamkową częścią rzeczywistej i ~ będąc jedną z następujących relacji = , < lub ≤ .

Pierwszy rodzaj ograniczeń zapewnia $spełniają$$​​i$ te same Rzeczywiście, jeśli i ${\ Displaystyle \ nu _ {1} (x) = 0,5}$ i ${\ Displaystyle \ nu _ {2} (x) = 1}$ , to tylko drugie zadanie spełnia ${\ displaystyle x = 1}$ . Z drugiej strony, jeśli ${\ Displaystyle \ nu _ {1} (x) = 0,5}$ i ${\ Displaystyle \ nu _ {2} (x) = 0,6}$ , oba zadania spełniają dokładnie ten sam zestaw ograniczeń, ponieważ ograniczenia używają tylko stałych całkowitych.

Drugi rodzaj ograniczeń zapewnia, że ​​przyszłość dwóch zadań spełnia te same ograniczenia. Na przykład niech ${\ Displaystyle \ nu _ {1} = \ {x \ mapsto 0,5, y \ mapsto 0,6 \}}$ i ${\ Displaystyle \ nu _ {2} = \ {x \ mapsto 0,5, y \ mapsto 0,4 \}}$ . Wtedy ograniczenie ${\ Displaystyle y = 1 \ land x <1}$ jest ostatecznie usatysfakcjonowany przyszłością bez resetowania $zegara ,$ nie przyszłością $nu _{2}}$${\ Displaystyle \$ bez resetowania zegara.

Jawna definicja regionu

Podczas gdy poprzednia definicja pozwala na sprawdzenie, czy dwa przypisania należą do tego samego regionu, nie pozwala na łatwe przedstawienie regionu jako struktury danych. Podana poniżej trzecia definicja pozwala na podanie kanonicznego kodowania regionu.

Region można jawnie zdefiniować jako strefę, używając zestawu równań i nierówności spełniających następujące ograniczenia: ${\ displaystyle S}$

• dla każdego ${\ Displaystyle x \ w C}$ S $\ Displaystyle S}$ zawiera albo: x ∈ do {\ Displaystyle x \ w C}
  • ${\ Displaystyle x = c}$ dla pewnej liczby całkowitej ${\ Displaystyle 0 \ równoważnik c \ równoważnik c_ {x}}$
  • ${\ Displaystyle x \ in (c, c + 1)}$ dla pewnej liczby całkowitej ${\ Displaystyle 0 \ równoważnik c <c_ {x}}$ ,
  • ${\ Displaystyle x> c_ {x}}$ ,
• ponadto dla każdej pary zegarów ${\ Displaystyle x, y \ w C}$${\ Displaystyle x \ w (c, c + 1)}$$gdzie$ zawiera ograniczenia postaci i ${\ Displaystyle y \ in (c ', c' + 1)}$ , a następnie ${\ Displaystyle S}$ zawiera (w) równość postaci ${\ Displaystyle \ {x \} \ sim \ {y \}$$}$ gdzie jest = , < lub ≤ .

Ponieważ $_$$z$ i ostatnie $jest$ _

Definicja ta pozwala na zakodowanie regionu jako struktury danych. Wystarczy dla każdego zegara określić, do którego przedziału należy i przypomnieć kolejność ułamkowej części zegarów, które należą do otwartego przedziału o długości 1. Wynika z tego, że rozmiar tej struktury wynosi ${\ Displaystyle O \ lewo (\ suma \ log (c_ {k}) + | C | \ log (| C |) \ prawo)}$ z ${\ displaystyle | C|}$ liczba zegarów.

Czasowa bisymulacja

Podajmy teraz trzecią definicję regionów. Chociaż ta definicja jest bardziej abstrakcyjna, jest to również powód, dla którego regiony są używane w sprawdzaniu modelu. Intuicyjnie definicja ta mówi, że dwa przypisania zegara należą do tego samego regionu, jeśli różnice między nimi są takie, że żaden automat czasowy nie może ich zauważyć. Biorąc pod uwagę dowolny przebieg $regionie$ się od przypisania $zegara$ dla każdego innego przypisania $w tym samym$ bieg ${\ displaystyle r'}$ , przechodząc przez te same miejsca, czytając te same litery, gdzie jedyną różnicą jest to, że czas oczekiwania między dwoma kolejnymi przejściami może być inny, a zatem kolejne zmiany zegara są różne.

Formalna definicja jest teraz podana. $pod$$przypisania$ zestaw zegara $, dwa przypisania dwa$ zegarów i do tego samego regionu, jeśli $c_$ czasowy $}}$ \ displaystyle $x$ , biorąc pod uwagę dowolną lokalizację ${\ Displaystyle \ ell}$ z ${\ Displaystyle {\ mathcal {A}}}$ istnieje bisymulacja czasowa między stanami rozszerzonymi ${\ Displaystyle (\ ell, \ nu _ {1})}$ i ${\ Displaystyle (\ ell, \ nu _ {2})}$ . Mówiąc dokładniej, ta bisymulacja zachowuje litery i lokalizacje, ale nie dokładne przypisania zegara.

Operacja na regionach

Niektóre operacje są teraz zdefiniowane w regionach: zresetowanie niektórych zegarów i pozwolenie na upływ czasu.

Resetowanie zegarów

Biorąc pod uwagę region zdefiniowany przez zestaw (nie) równań $i$ zestaw zegarów, region podobny do $α$${\ displaystyle \ alpha}$$C}$$,$ w którym zegary są uruchamiane, jest teraz zdefiniowany Region ten jest oznaczony przez $\ Displaystyle \ alpha [C'\ mapsto 0]}$ , jest zdefiniowany przez następujące ograniczenia:

• każde ograniczenia nie zawierające zegara, S $displaystyle S$$}$
• ograniczenia ${\ Displaystyle x = 0}$ dla ${\ Displaystyle x \ w C '}$ .

Zbiór przypisań zdefiniowany przez $[ do$ przypisań $C '\ mapsto 0$ dla ${\ Displaystyle \ nu \ in \ alpha}$ .

Następca czasu

$uwagę$ region , regiony, które można osiągnąć bez resetowania zegara, nazywane są następnikami czasu $\ displaystyle \ alpha}$ . Podano teraz dwie równoważne definicje.

Definicja

Region zegara $zegara,$ następcą czasowym innego regionu jeśli dla każdego zadania istnieje jakiś pozytywny $Displaystyle \ nu \ in \$$\$ rzeczywisty ${\ Displaystyle t _ {\ nu, \ alfa '}> 0}$ taki, że ${\ Displaystyle \ nu + t _ {\ nu, \ alfa '} \ w \ alfa '}$ .

Zauważ, że nie oznacza to, że ${\ Displaystyle \ alfa + t_ {\ nu, \ alfa '} = \ alfa '}$ . Na przykład region zdefiniowany przez zestaw ograniczeń ${$${\ Displaystyle \ {0 <x <1,0 <y <$ ma następcę czasowego ${\ Displaystyle \ alpha '}$ zdefiniowany przez zestaw ograniczeń ${\ Displaystyle \ {0 <x <1, y = 1 \}}$ . $nu (y)}$ , dla każdego wystarczy przyjąć $y$$t_ {\ nu, \ alfa '} =$ . Jednak nie istnieje żaden prawdziwy $}$$Displaystyle \ alfa + t \ subseteq \$ takie, że lub nawet takie, że $t$ alpha rzeczywiście, $definiuje$ , podczas $definiuje$ .

Obliczalna definicja

Podana teraz druga definicja pozwala na jawne obliczenie zbioru następcy czasowego regionu, określonego przez jego zestaw ograniczeń.

$pod$ uwagę region $zdefiniowany$ jako zbiór ograniczeń , zdefiniujmy jego zbiór następców czasowych W tym celu wymagane są następujące zmienne. Niech ${\ displaystyle T \ subseteq S}$ zbiór ograniczeń postaci ${\ displaystyle S}$${\ displaystyle x_ {i} = c_ {i}}$ . Niech ${\ displaystyle Y \ subseteq C}$ zestaw zegarów $y}$$displaystyle$ takie, że zawiera ograniczenie $y}}$ . Niech $\ setminus Y}$$\displaystyle \{x\}<\{z\}}$$}$$C$ zestaw zegarów taki ograniczeń postaci w ${\ displaystyle S}$ .

Jeśli $pusty$ , $.$ swoim własnym następcą czasowym Jeśli $displaystyle Y = C}$${\ displaystyle \ alpha$ to jest jedynym następcą czasowym $}$ . W przeciwnym ${\ displaystyle \ alpha$ istnieje najmniejszy następca czasowy nie równy $}$ . Najmniejszy następca czasu, jeśli ${\ displaystyle T}$ jest niepusty, zawiera:

• ograniczenia ${\ Displaystyle S \ setminus T}$
• ${\ Displaystyle x_ {i}> c_ {i}}$ ,
• ${\ Displaystyle \ {x_ {i} \} = \ {x_ {j} \}}$ i
• dla każdego $> c_ {y}}$$\ displaystyle$ r ${\ displaystyle x_ {i}<y }$ nie należy do ${\ displaystyle S}$ , ograniczenie .

Jeśli jest pusty, najmniejszy następnik czasowy jest zdefiniowany przez następujące ograniczenia: ${\ displaystyle T}$

• ograniczenia $displaystyle Z}$ zegarów ${\$ ,
• ograniczenie $} ,$${\ Displaystyle Z \ w Z}$$Displaystyle$$dla$ każdego do z .

Nieruchomości

Jest co najwyżej ${\ Displaystyle | C |! 2 ^ {| C |} \ prod _ {x \ w C} (2c_ {x} + 2)}$ regiony, gdzie ${\ displaystyle | C |}$ to liczba zegarów.

Automat regionu

$pod$ uwagę automat czasowy $,$ jego automat regionu jest automatem skończonym lub automatem Büchi który akceptuje nieokreślony . Ten automat jest podobny do $zegary$ są zastępowane przez region. Intuicyjnie automat regionu jest tworzony jako iloczyn $regionu$ . Ten wykres regionu jest zdefiniowany jako pierwszy.

Wykres regionu

Graf regionu jest ukorzenionym grafem skierowanym, który modeluje zestaw możliwych wycen zegara podczas przebiegu autoamtonu czasowego. Jest zdefiniowany w następujący sposób:

• jego węzłami są regiony,
• jego pierwiastkiem jest region początkowy $}$ zdefiniowany przez zestaw ograniczeń, ${\ Displaystyle \ {x = 0 \ mid x \ w C \$ }
• zbiór krawędzi to ${\ Displaystyle (\ alfa, \ alfa '[C' \ mapsto 0]}}$ , dla następcy czasu ${\ Displaystyle \ alfa '}$ z ${\ displaystyle \ alpha}$ .

Automat regionu

Niech ${\ Displaystyle {\ mathcal {A}} = \ langle \ Sigma, L, L_ {0}, C, F, E \ rangle}$ automat czasowy . Dla każdego zegara $Displaystyle c$ będzie $}$ liczba $do {\ Displaystyle x \ in$ taka, że ​​istnieje strażnik postaci ${\ Displaystyle x \ sim c}$ w ${\ Displaystyle {\ mathcal {A}}}$ . Automat regionu , $automatem$ przez skończonym lub automatem Büchi $który$ iloczynem ${\ displaystyle {\ mathcal {A}}}$ i wykresu regionu zdefiniowanego powyżej. Oznacza to, że każdy stan automatu regionu jest parą zawierającą położenie ${\ displaystyle {\ mathcal {A}}}$ i region. Ponieważ przypisanie dwóch zegarów należących do tego samego regionu spełnia tę samą straż, każdy region zawiera wystarczającą ilość informacji, aby zdecydować, które przejścia można wykonać.

Formalnie automat regionu jest zdefiniowany w następujący sposób:

• jego alfabet to , Σ $\ displaystyle \ Sigma}$
• jego zbiór stanów to $}$ }
• jego zbiór stanów to ${\ Displaystyle L_ {0} \ razy \ {\ alfa _ {0} \}}$ z regionem początkowym, L × { $} {\ Displaystyle L_ {0} \ razy \ {\ alfa _ {0} \}}$
• jego zestaw akceptujących stanów to ${\ displaystyle F \ razy {\ mathcal {R}}}$ ,
• jego relacja przejściowa $\$ ( $ell, \ alfa), a, (\ ell ',\alpha '[C'\mapsto 0]))}$ , dla $\ Displaystyle \$ a $, g, C ', \ ell ') \ in E}$$alpha '}$ , że jest następcą czasowym ${\ displaystyle \ alpha}$ .

R ${\ Displaystyle R = (\ ell _ {0}, \ nu _ {0}) {\ xrightarrow [{t_$$\ mathcal {A}}}$ Displaystyle { ${\ Displaystyle (\ ell _ {0}, [\ nu _ {0}]) {\ xrightarrow {\ sigma _ {1}}} (\ ell _ {1}, [\ nu _ { 1}]) \ kropki}$ jest oznaczony ${\ Displaystyle [r]}$ , jest to przebieg ${\ Displaystyle R ({\ mathcal {A}})}$ i akceptuje wtedy i tylko wtedy, gdy ${\ displaystyle r}$ akceptuje. Wynika z tego, że ${\ Displaystyle L (R ({\ mathcal {A}})) = \ operatorname {Untime} (L ({\ mathcal {A}}))}$ . $,$ szczególności słowo czasowe wtedy i tylko $gdy$ słowo Co więcej, akceptujący przebieg $A}}}$ przebiegu . \ displaystyle ${ \ mathcal$