Region (kontrola modelu) - Region (model checking)

v kontrola modelu, pole počítačová věda, a kraj je konvexní mnohostěn v ${ displaystyle mathbb {R} ^ {d}}$ pro nějakou dimenzi ${ displaystyle d}$ a přesněji a zóna, uspokojující určitou vlastnost minimality. Rozdělení oblastí ${ displaystyle mathbb {R} ^ {d}}$ .

Sada zón závisí na sadě ${ displaystyle K}$ omezení formuláře ${ 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. Oblasti jsou definovány tak, že pokud jsou dva vektory ${ displaystyle { vec {x}}}$ a ${ displaystyle { vec {x}} '}$ patří do stejné oblasti, pak splňují stejná omezení ${ displaystyle K}$ . Navíc, když jsou tyto vektory považovány za n-tici hodiny, oba vektory mají stejnou sadu možných futurů. Intuitivně to znamená, že jakýkoli časovaná výroková časová logika -formule, nebo časovaný automat nebo signální automat pouze s použitím omezení ${ displaystyle K}$ nelze rozlišit oba vektory.

Sada regionů umožňuje vytvořit automat regionu, což je řízený graf ve kterém každý uzel je oblast a každá hrana ${ displaystyle r to r '}$ ujisti se že ${ displaystyle r '}$ je možná budoucnost ${ displaystyle r}$ . Vezmeme produkt tohoto regionu automatu a časovaný automat ${ displaystyle { mathcal {A}}}$ který přijímá jazyk ${ displaystyle L}$ vytváří konečný automat nebo a Büchi automat který přijímá nečasovaný ${ displaystyle L}$ . Zejména umožňuje snížit problém prázdnoty pro ${ displaystyle { mathcal {A}}}$ k problému prázdnoty pro konečný nebo Büchiho automat. Tuto techniku používá například software UPPAAL.^[1]

Definice

Nechat ${ displaystyle C = {x_ {1}, tečky, x_ {d} }}$ sada hodiny. Pro každého ${ displaystyle x in mathbb {N}}$ nechat ${ displaystyle c_ {x} in mathbb {N}}$ . Intuitivně toto číslo představuje horní mez na hodnotách, na které hodiny ${ displaystyle x}$ lze porovnat. Definice oblasti nad hodinami ${ displaystyle C}$ používá tato čísla ${ displaystyle c_ {x}}$ je. Nyní jsou uvedeny tři ekvivalentní definice.

Vzhledem k přiřazení hodin ${ displaystyle nu}$ , ${ displaystyle [ nu]}$ označuje region, ve kterém ${ displaystyle nu}$ patří. Sada regionů je označena ${ displaystyle { mathcal {R}}}$ .

Ekvivalence přiřazení hodin

První definice umožňuje snadno otestovat, zda dvě přiřazení patří do stejné oblasti.

Oblast může být definována jako třída ekvivalence pro nějaký vztah ekvivalence. Dvě přiřazení hodin ${ displaystyle nu _ {1}}$ a ${ displaystyle nu _ {2}}$ jsou ekvivalentní, pokud splňují následující omezení:^[2]^:

${ displaystyle nu _ {1} (x) sim c}$ iff ${ displaystyle nu _ {2} (x) sim c}$ , pro každého ${ displaystyle x v C}$ a ${ displaystyle 0 leq c leq c_ {x}}$ celé číslo a ~ je jedním z následujících vztahů =, < nebo ≤.
${ displaystyle { nu _ {1} (x) } sim { nu _ {1} (y) }}$ iff ${ displaystyle { nu _ {2} (x) } sim { nu _ {2} (y) }}$ , pro každého ${ displaystyle x, y v C}$ , ${ displaystyle nu _ {1} (x) leq c_ {x}}$ , ${ displaystyle nu _ {1} (y) leq c_ {y}}$ , ${ displaystyle {r }}$ být zlomková část skutečný ${ displaystyle r}$ a ~ je jedním z následujících vztahů =, < nebo ≤.

První druh omezení to zajišťuje ${ displaystyle nu _ {1}}$ a ${ displaystyle nu _ {2}}$ splňuje stejná omezení. Opravdu, pokud ${ displaystyle nu _ {1} (x) = 0,5}$ a ${ displaystyle nu _ {2} (x) = 1}$ , pak vyhovuje pouze druhé zadání ${ displaystyle x = 1}$ . Na druhou stranu, pokud ${ displaystyle nu _ {1} (x) = 0,5}$ a ${ displaystyle nu _ {2} (x) = 0,6}$ , obě přiřazení splňují přesně stejnou sadu omezení, protože omezení používají pouze integrální konstanty.

Druhý druh omezení zajišťuje, že budoucnost dvou přiřazení splňuje stejná omezení. Například nechte ${ displaystyle nu _ {1} = {x mapsto 0,5, y mapsto 0,6 }}$ a ${ displaystyle nu _ {2} = {x mapsto 0,5, y mapsto 0,4 }}$ . Potom omezení ${ displaystyle y = 1 země x <1}$ je nakonec spokojen s budoucností ${ displaystyle nu _ {1}}$ bez vynulování hodin, ale ne do budoucnosti ${ displaystyle nu _ {2}}$ bez vynulování hodin.

Výslovná definice oblasti

Zatímco předchozí definice umožňuje otestovat, zda dvě přiřazení patří do stejné oblasti, neumožňuje snadno reprezentovat oblast jako datovou strukturu. Třetí definice uvedená níže umožňuje poskytnout kanonické kódování oblasti.

Oblast lze explicitně definovat jako a zóna pomocí sady ${ displaystyle S}$ rovnic a nerovnic splňujících následující omezení:

pro každého ${ displaystyle x v C}$ $x v C$ , ${ displaystyle S}$ $S$ obsahuje buď:
- ${ displaystyle x = c}$ pro celé číslo ${ displaystyle 0 leq c leq c_ {x}}$
- ${ displaystyle x in (c, c + 1)}$ pro celé číslo ${ displaystyle 0 leq c$ ,
- ${ displaystyle x> c_ {x}}$ ,
dále pro každý pár hodin ${ displaystyle x, y v C}$ , kde ${ displaystyle S}$ obsahuje omezení formuláře ${ displaystyle x in (c, c + 1)}$ a ${ displaystyle y in (c ', c' + 1)}$ , pak ${ displaystyle S}$ obsahuje (ne) rovnost formuláře ${ displaystyle {x } sim {y }}$ s ${ displaystyle sim}$ být buď =, < nebo ≤.

Od kdy ${ displaystyle c}$ a ${ displaystyle c '}$ jsou pevné, poslední omezení je ekvivalentní s ${ displaystyle x sim y + c-c '}$ .

Tato definice umožňuje kódovat oblast jako datovou strukturu. Postačuje pro každé hodiny uvést, do kterého intervalu patří, a vyvolat pořadí zlomkové části hodin, které patří do otevřeného intervalu délky 1. Z toho vyplývá, že velikost této struktury je ${ displaystyle O left ( sum log (c_ {k}) + | C | log (| C |) right)}$ s ${ displaystyle | C |}$ počet hodin.

Časovaná bisimulace

Pojďme nyní uvést třetí definici regionů. I když je tato definice abstraktnější, je to také důvod, proč se při kontrole modelu používají regiony. Tato definice intuitivně uvádí, že dvě přiřazení hodin patří do stejné oblasti, pokud jsou rozdíly mezi nimi takové, že ne časovaný automat může si jich všimnout. Vzhledem k jakémukoli běhu ${ displaystyle r}$ počínaje přiřazením hodin ${ displaystyle nu}$ , pro jakýkoli jiný úkol ${ displaystyle nu '}$ ve stejné oblasti je běh ${ displaystyle r '}$ , procházet stejnými místy, číst stejná písmena, přičemž jediný rozdíl je v tom, že doba čekání mezi dvěma po sobě jdoucími přechody se může lišit, a tudíž se liší i postupné variace hodin.

Nyní je uvedena formální definice. Vzhledem k sadě hodin ${ displaystyle C}$ , dvě přiřazení dvě přiřazení hodin ${ displaystyle nu _ {1}}$ a ${ displaystyle nu _ {2}}$ patří do stejné oblasti, pokud pro každou z nich časovaný automat ${ displaystyle { mathcal {A}}}$ ve kterém stráže nikdy nesrovnávají hodiny ${ displaystyle x}$ na číslo větší než ${ displaystyle c_ {x}}$ , vzhledem k libovolnému umístění ${ displaystyle ell}$ z ${ displaystyle { mathcal {A}}}$ , existuje časovaný bisimulace mezi rozšířenými státy ${ displaystyle ( ell, nu _ {1})}$ a ${ displaystyle ( ell, nu _ {2})}$ . Přesněji řečeno, tato bisimulace zachovává písmena a umístění, ale ne přesné přiřazení hodin.^[1]^:7

Provoz v regionech

Některé operace jsou nyní definovány v regionech: Resetování některých jeho hodin a nechání plynout čas.

Resetování hodin

Vzhledem k regionu ${ displaystyle alpha}$ definovaný množinou (ne) rovnic ${ displaystyle S}$ a sada hodin ${ displaystyle C ' subseteq C}$ , region podobný ${ displaystyle alpha}$ ve kterém hodiny ${ displaystyle C '}$ jsou restartovány, je nyní definováno. Tato oblast je označena ${ displaystyle alpha [C ' mapsto 0]}$ , je definován následujícími omezeními:

každé omezení ${ displaystyle S}$ neobsahující hodiny ${ displaystyle x}$ ,
omezení ${ displaystyle x = 0}$ pro ${ displaystyle x v C '}$ .

Sada přiřazení definovaná ${ displaystyle alpha [C ' mapsto 0]}$ je přesně sada úkolů ${ displaystyle nu [C ' mapsto 0]}$ pro ${ displaystyle nu in alpha}$ .

Časový nástupce

Vzhledem k regionu ${ displaystyle alpha}$ , regiony, kterých lze dosáhnout bez vynulování hodin, se nazývají časové nástupce ${ displaystyle alpha}$ . Nyní jsou uvedeny dvě ekvivalentní definice.

Definice

Region hodin ${ displaystyle alpha '}$ je časovým nástupcem jiné hodinové oblasti ${ displaystyle alpha}$ pokud pro každý úkol ${ displaystyle nu in alpha}$ , existuje nějaký pozitivní reálný ${ displaystyle t _ { nu, alpha '}> 0}$ takhle ${ displaystyle nu + t _ { nu, alfa '} v alfa'}$ .

Všimněte si, že to neznamená ${ displaystyle alpha + t _ { nu, alpha '} = alfa'}$ . Například region ${ displaystyle alpha}$ definovaný množinou omezení ${ displaystyle {0$ má časového nástupce ${ displaystyle alpha '}$ definovaný množinou omezení ${ displaystyle {0$ . Ve skutečnosti pro každého ${ displaystyle nu in alpha}$ , to stačí vzít ${ displaystyle t _ { nu, alpha '} = 1- nu (y)}$ . Neexistuje však žádný skutečný ${ displaystyle t}$ takhle ${ displaystyle alpha + t = alpha '}$ nebo dokonce takové ${ displaystyle alpha + t subseteq alpha '}$ ; Vskutku, ${ displaystyle alpha}$ definuje trojúhelník while ${ displaystyle alpha '}$ definuje segment.

Vypočitatelná definice

Druhá definice, která je nyní uvedena, umožňuje explicitně vypočítat sadu časového nástupce oblasti, danou její sadou omezení.

Vzhledem k regionu ${ displaystyle alpha}$ definována jako sada omezení ${ displaystyle S}$ definujme jeho sadu časových nástupců. K tomu jsou nutné následující proměnné. Nechat ${ displaystyle T subseteq S}$ soubor omezení ${ displaystyle S}$ formuláře ${ displaystyle x_ {i} = c_ {i}}$ . Nechat ${ displaystyle Y subseteq C}$ sada hodin ${ displaystyle y}$ takhle ${ displaystyle S}$ obsahuje omezení ${ displaystyle y> c_ {y}}$ . Nechat ${ displaystyle Z subseteq C setminus Y}$ sada hodin ${ displaystyle {z }}$ taková, že neexistují žádná omezení formy ${ displaystyle {x } < {z }}$ v ${ displaystyle S}$ .

Li ${ displaystyle T}$ je prázdný, ${ displaystyle alpha}$ je jeho vlastním časovým nástupcem. Li ${ displaystyle Y = C}$ , pak ${ displaystyle alpha}$ je jediným časovým nástupcem ${ displaystyle alpha}$ . Jinak je tu nejméně časově nástupce ${ displaystyle alpha}$ nerovná se ${ displaystyle alpha}$ . Nejméně nástupce času, pokud ${ displaystyle T}$ není prázdný, obsahuje:

omezení ${ displaystyle S setminus T}$
${ displaystyle x_ {i}> c_ {i}}$ ,
${ displaystyle {x_ {i} } = {x_ {j} }}$ , a
pro každého ${ displaystyle y}$ takhle ${ displaystyle y> c_ {y}}$ nepatří ${ displaystyle S}$ omezení ${ displaystyle x_ {i}$ .

Li ${ displaystyle T}$ je prázdný, nejmenší časový nástupce je definován následujícími omezeními:

omezení ${ displaystyle S}$ nepoužívat hodiny ${ displaystyle Z}$ ,
omezení ${ displaystyle z = c + 1}$ , pro každé omezení ${ displaystyle c$ v ${ displaystyle S}$ , s ${ displaystyle z v Z}$ .

Vlastnosti

Existuje nanejvýš ${ displaystyle | C |! 2 ^ {| C |} prod _ {x v C} (2c_ {x} +2)}$ regiony, kde ${ displaystyle | C |}$ je počet hodin.^[2]^:203

Region automat

Vzhledem k časovanému automatu ${ displaystyle { mathcal {A}}}$ , své automat regionu je konečný automat nebo a Büchi automat který přijímá nečasovaný ${ displaystyle L}$ . Tento automat je podobný ${ displaystyle { mathcal {A}}}$ , kde jsou hodiny nahrazeny oblastí. Regionální automat je intuitivně konstruován jako produkt ${ displaystyle { mathcal {A}}}$ a regionálního grafu. Tento regionový graf je definován jako první.

Graf regionu

The region region je zakořeněný řízený graf, který modeluje množinu možných hodinových hodnot během běhu časovaného autoamtonu. Je definován takto:

jeho uzly jsou regiony,
jeho kořen je počáteční oblast ${ displaystyle alpha _ {0}}$ , definovaný množinou omezení ${ displaystyle {x = 0 mid x v C }}$ ,
sada hran je ${ displaystyle ( alpha, alpha '[C' mapsto 0])}$ , pro ${ displaystyle alpha '}$ časový nástupce ${ displaystyle alpha}$ .

Region automat

Nechat ${ displaystyle { mathcal {A}} = langle Sigma, L, L_ {0}, C, F, E rangle}$ A časovaný automat. Pro každé hodiny ${ displaystyle x v C}$ , nechť ${ displaystyle c_ {x}}$ největší počet ${ displaystyle c}$ takovým, že existuje stráž formy ${ displaystyle x sim c}$ v ${ displaystyle { mathcal {A}}}$ . The automat regionu z ${ displaystyle { mathcal {A}}}$ , označeno ${ displaystyle R ({ mathcal {A}})}$ je konečný nebo Büchi automat, který je v podstatě produktem ${ displaystyle { mathcal {A}}}$ a regionálního grafu definovaného výše. To znamená, že každý stav regionálního automatu je dvojice obsahující loctaion z ${ displaystyle { mathcal {A}}}$ a region. Jelikož přiřazení dvou hodin patřících do stejné oblasti splňuje stejnou stráž, každá oblast obsahuje dostatek informací k rozhodnutí, které přechody lze provést.

Formálně je automat oblasti definován takto:

jeho abeceda je ${ displaystyle Sigma}$ ,
jeho sada států je ${ displaystyle L times { mathcal {R}}}$ ,
jeho sada států je ${ displaystyle L_ {0} krát { alpha _ {0} }}$ s ${ displaystyle alpha _ {0}}$ počáteční oblast,
jeho sada přijímajících států je ${ displaystyle F times { mathcal {R}}}$ ,
jeho přechodový vztah ${ displaystyle delta}$ obsahuje ${ displaystyle (( ell, alpha), a, ( ell ', alpha' [C ' mapsto 0]))}$ , pro ${ displaystyle ( ell, a, g, C ', ell') v E}$ , takový, že ${ displaystyle gamma modely alpha '}$ a ${ displaystyle alpha '}$ je časovým nástupcem ${ displaystyle alpha}$ .

Vzhledem k jakémukoli běhu ${ displaystyle r = ( ell _ {0}, nu _ {0}) { xrightarrow [{t_ {1}}] { sigma _ {1}}} ( ell _ {1}, nu _ {1}) dots}$ z ${ displaystyle { mathcal {A}}}$ , sekvence ${ displaystyle ( ell _ {0}, [ nu _ {0}]) { xrightarrow { sigma _ {1}}} ( ell _ {1}, [ nu _ {1}]) tečky}$ je označen ${ displaystyle [r]}$ , je to běh ${ displaystyle R ({ mathcal {A}})}$ a přijímá pouze tehdy, když ${ displaystyle r}$ přijímá^[2]^:207. Z toho vyplývá, že ${ displaystyle L (R ({ mathcal {A}})) = operatorname {Untime} (L ({ mathcal {A}}))}$ . Zejména, ${ displaystyle { mathcal {A}}}$ přijímá časované slovo právě tehdy ${ displaystyle R ({ mathcal {A}})}$ přijímá slovo. Dále přijímací běh ${ displaystyle { mathcal {A}}}$ lze vypočítat z přijímajícího běhu ${ displaystyle R ({ mathcal {A}})}$ .

Reference

^ ^A ^b Bengtsson, Johan; Yi, Wang L (2003). „Načasované automaty: sémantika, algoritmy a nástroje“. Přednášky o souběžnosti a Petriho sítích. 3098: 87–124. doi:10.1007/978-3-540-27755-2_3.
^ ^A ^b ^C Alur, Rajeev; Dill, David L (25. dubna 1994). „Teorie časovaných automatů“ (PDF). Teoretická informatika. 126 (2): 183–235. doi:10.1016/0304-3975(94)90010-8.

[Timed_Automata:_Semantics,_Algorithm_And_Tools-1] A ^b Bengtsson, Johan; Yi, Wang L (2003). „Načasované automaty: sémantika, algoritmy a nástroje“. Přednášky o souběžnosti a Petriho sítích. 3098: 87–124. doi:10.1007/978-3-540-27755-2_3.

[AlurDill-2] A ^b ^C Alur, Rajeev; Dill, David L (25. dubna 1994). „Teorie časovaných automatů“ (PDF). Teoretická informatika. 126 (2): 183–235. doi:10.1016/0304-3975(94)90010-8.

[1]

[2]