Hodiny (kontrola modelu) - Clock (model checking)

v kontrola modelu, podpole z počítačová věda, a hodiny je matematický objekt používaný k modelování času. Přesněji řečeno, hodiny měří, kolik času uplynulo od určité události, v tomto smyslu jsou hodiny přesněji abstrakcí stopky. V modelu určitého konkrétního programu může být hodnotou hodin buď čas od spuštění programu, nebo čas od okamžiku, kdy v programu došlo k určité události. Tyto hodiny se používají v definici časovaný automat, signální automat, časovaná výroková časová logika a časová logika hodin. Používají se také v programech, jako jsou UPPAAL které implementují časované automaty.^[1]

Obecně platí, že model systému používá mnoho hodin. Tyto vícenásobné hodiny jsou nutné, aby bylo možné sledovat omezený počet událostí. Všechny tyto hodiny jsou synchronizovány. To znamená, že rozdíl v hodnotě mezi dvěma pevnými hodinami je konstantní, dokud není jeden z nich restartován. V jazyce elektroniky to znamená, že hodiny chvění je null.

Příklad

Předpokládejme, že chceme modelovat výtah v budově s deseti podlažími. Náš model může mít ${ displaystyle n}$ hodiny ${ displaystyle c_ {0}, tečky, c_ {9}}$ , takže hodnota hodin ${ displaystyle c_ {i}}$ je čas, kdy někdo čekal na výtah v patře ${ displaystyle i}$ . Tyto hodiny se spustí, když někdo zavolá výtahem v patře ${ displaystyle i}$ (a výtah nebyl v tomto patře od poslední návštěvy tohoto patra již spuštěn). Tyto hodiny lze vypnout, když výtah dorazí na podlahu ${ displaystyle i}$ . V tomto příkladu vlastně potřebujeme deset odlišných hodin, protože potřebujeme sledovat deset nezávislých událostí. Další hodiny ${ displaystyle s}$ lze použít ke kontrole, kolik času strávil výtah v konkrétním patře.

Model tohoto výtahu pak může pomocí těchto hodin tvrdit, zda program výtahu splňuje vlastnosti, jako například „za předpokladu, že výtah není udržován na podlaze déle než patnáct sekund, pak na něj nemusí nikdo čekat déle než tři minuty ". Aby bylo možné zkontrolovat, zda toto tvrzení platí, stačí zkontrolovat, že při každém spuštění modelu, ve kterém hodiny ${ displaystyle s}$ je vždy menší než patnáct sekund, každé hodiny ${ displaystyle c_ {i}}$ je vypnutý, než dosáhne tří minut.

Definice

Formálně sada ${ displaystyle X}$ hodin je prostě konečná sada^[1]^:191. Každý prvek sady hodin se nazývá hodiny. Intuitivně jsou hodiny podobné proměnné v logika prvního řádu, je to prvek, který lze použít v logickém vzorci a který může mít řadu různých hodnot.

Oceňování hodin

A ocenění hodin nebo interpretace hodin^[1]^:193 ${ displaystyle nu}$ přes ${ displaystyle X = {x_ {1}, tečky, x_ {n} }}$ je obvykle definována jako funkce z ${ displaystyle X}$ do souboru nezáporných reálných. Ekvivalentně lze ocenění považovat za bod v ${ displaystyle mathbb {R} _ { geq 0} ^ {n}}$ .

The počáteční přiřazení ${ displaystyle nu _ {0}}$ je konstantní funkce posílající každé hodiny na 0. Intuitivně představuje počáteční čas programu, kde jsou všechny hodiny inicializovány současně.

Vzhledem k přiřazení hodin ${ displaystyle nu}$ a skutečný ${ displaystyle t geq 0}$ , ${ displaystyle nu + t}$ označuje přiřazení hodin odesílajících každé hodiny ${ displaystyle x v C}$ na ${ displaystyle nu (x) + t}$ . Intuitivně představuje ocenění ${ displaystyle nu}$ po čemž ${ displaystyle t}$ uplynuly časové jednotky.

Vzhledem k podmnožině ${ displaystyle r subseteq C}$ hodin, ${ displaystyle nu [r rightarrow 0]}$ označuje přiřazení podobné ${ displaystyle nu}$ ve kterém hodiny ${ displaystyle r}$ jsou resetovány. Formálně, ${ displaystyle nu [r rightarrow 0]}$ odešle každé hodiny ${ displaystyle x in r}$ na 0 a každé hodiny ${ displaystyle x not in r}$ na ${ displaystyle nu (x)}$ .

Neaktivní hodiny

Program UPPAAL zavést pojem neaktivní hodiny.^[2] Hodiny jsou v určitém čase neaktivní, pokud neexistuje budoucnost, ve které by byla kontrolována hodnota hodin, aniž by byly nejprve resetovány. V našem příkladu výše hodiny ${ displaystyle c_ {i}}$ je považováno za neaktivní, když výtah dorazí do patra ${ displaystyle i}$ , a zůstane neaktivní, dokud někdo nezavolá výtahem v patře ${ displaystyle i}$ .

Při povolení neaktivních hodin může ocenění přiřadit hodiny ${ displaystyle x}$ na nějakou zvláštní hodnotu ${ displaystyle bot}$ k označení, že je neaktivní. Li ${ displaystyle nu (x) = bot}$ pak ${ displaystyle ( nu + t) (x)}$ také se rovná ${ displaystyle bot}$ .

Omezení hodin

An omezení atomových hodin je prostě termín formy ${ displaystyle x sim c}$ , kde ${ displaystyle x}$ jsou hodiny, ${ displaystyle sim}$ je operátor porovnání, například <, ≤, = ≥ nebo>, a ${ displaystyle c in mathbb {N}}$ je integrální konstanta. V našem předchozím příkladu můžeme použít omezení atomových hodin ${ displaystyle c_ {i} leq 180}$ uvést, že osoba v patře ${ displaystyle i}$ čekal méně než tři minuty a ${ displaystyle s> 15}$ prohlásit, že výtah zůstal v nějakém patře déle než patnáct sekund. Ocenění ${ displaystyle nu}$ splňuje ocenění atomových hodin ${ displaystyle x sim c}$ kdyby a jen kdyby ${ displaystyle nu (x) sim c}$ .

A omezení hodin je buď konečný spojení omezení atomových hodin nebo je konstanta „true“ (kterou lze považovat za prázdnou spojku). Ocenění ${ displaystyle nu}$ vyhovuje hodinovému omezení ${ displaystyle bigwedge _ {i = 1} ^ {n} x_ {i} sim _ {i} c_ {i}}$ pokud splňuje každé omezení atomových hodin ${ displaystyle x_ {i} sim _ {i} c_ {i}}$ .

Diagonální omezení

V závislosti na kontextu může mít také omezení atomové hodiny ${ displaystyle x_ {i} sim x_ {j} + c}$ . Takové omezení se nazývá diagonální omezení, protože ${ displaystyle x_ {1} = x_ {2} + c}$ definuje diagonální čáru v ${ displaystyle mathbb {R} _ { geq 0} ^ {2}}$ .

Povolení diagonálních omezení může umožnit zmenšit velikost vzorce nebo automatu použitého k popisu systému. Složitost algoritmu se však může zvýšit, pokud jsou povolena diagonální omezení. Ve většině systémů využívajících hodiny povolení diagonálního omezení nezvýší expresivitu logiky. Nyní vysvětlíme, jak zakódovat takové omezení pomocí booleovské proměnné a ne-diagonálního omezení.

Diagonální omezení ${ displaystyle x_ {i} sim x_ {j} + c}$ lze simulovat pomocí ne-diagonálních omezení následujícím způsobem. Když ${ displaystyle x_ {j}}$ je resetováno, zkontrolujte, zda ${ displaystyle x_ {i} sim c}$ drží nebo ne. Připomeňte si tyto informace v booleovské proměnné ${ displaystyle b_ {i, j, c}}$ a vyměnit ${ displaystyle x_ {i} sim x_ {j} + c}$ touto proměnnou. Když ${ displaystyle x_ {i}}$ je resetováno, nastaveno ${ displaystyle b_ {i, j, c}}$ pravda, pokud ${ displaystyle sim}$ je ${ displaystyle sim}$

Způsob kódování logické proměnné závisí na systému, který používá hodiny. Například, UPPAAL podporuje booleovské proměnné přímo. Časované automaty a signální automaty může kódovat booleovskou hodnotu na svých místech. v časová logika hodin nad časovanými slovy může být logická proměnná kódována pomocí nových hodin ${ displaystyle x_ {i, j, c}}$ , jehož hodnota je 0 právě tehdy ${ displaystyle b_ {i, j, c}}$ je nepravdivé. To znamená, ${ displaystyle x_ {i, j, c}}$ se resetuje, pokud ${ displaystyle x_ {i, j, c}}$ má být nepravdivý. v časovaná výroková časová logika, vzorec ${ displaystyle x_ {i}. phi}$ , které se restartují ${ displaystyle x_ {i}}$ a poté vyhodnotí ${ displaystyle phi}$ , lze nahradit vzorcem ${ displaystyle x_ {i}. ((x_ {i} sim x_ {j} + c implikuje phi _ { top}) land ( neg x_ {i} sim x_ {j} + c znamená phi bot))}$ , kde ${ displaystyle phi _ { nahoru}}$ a ${ displaystyle phi _ { bot}}$ jsou kopie vzorců ${ displaystyle phi}$ , kde ${ displaystyle x_ {i} sim x_ {j} + c}$ jsou nahrazeny pravou a falešnou konstantou.

Sady definované omezeními hodin

Omezení hodin definuje sadu ocenění. V literatuře se uvažuje o dvou druzích takových sad.

A zóna je neprázdná sada ocenění splňující časové omezení. Zóny a omezení hodin jsou implementovány pomocí rozdílová vázaná matice.

Vzhledem k modelu ${ displaystyle M}$ , ve svých hodinových omezeních používá konečný počet konstant. Nechat ${ displaystyle K}$ být největší použitá konstanta. A kraj je neprázdná zóna, ve které není žádné omezení větší než ${ displaystyle K}$ jsou použity a navíc takové, že je minimální pro zařazení.

Viz také

Poznámky

^ ^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.
^ Behrmann, Gerd; David, Alexandre; Larsen, Kim G (28. listopadu 2006). „Výukový program pro Uppaal 4.0“ (PDF): 28. Citovat deník vyžaduje | deník = (Pomoc)

[AlurDill-1] 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.

[2] Behrmann, Gerd; David, Alexandre; Larsen, Kim G (28. listopadu 2006). „Výukový program pro Uppaal 4.0“ (PDF): 28. Citovat deník vyžaduje | deník = (Pomoc)

[1]

[2]