Dobře strukturovaný přechodový systém - Well-structured transition system

V počítačové vědě, konkrétně v oblasti formální ověření, dobře strukturované přechodové systémy (WSTS) jsou obecnou třídou systémů nekonečného stavu, pro které je mnoho problémů s ověřováním rozhodnutelné, vzhledem k existenci jakési objednat mezi stavy systému, který je kompatibilní s přechody systému. Lze použít výsledky rozhodovatelnosti WSTS Petriho sítě, ztrátové kanálové systémy a další.

Formální definice

Připomeňme, že a dobře kvazi-objednávání ${ displaystyle leq}$ na setu ${ displaystyle X}$ je kvazi objednávání (tj. a předobjednávka nebo reflexní, tranzitivní binární relace ) takový, že jakýkoli nekonečný sled prvků ${ displaystyle x_ {0}, x_ {1}, x_ {2}, ldots}$, z ${ displaystyle X}$ obsahuje rostoucí dvojici ${ displaystyle x_ {i} leq x_ {j}}$ s ${ displaystyle i$. Sada ${ displaystyle X}$ se říká, že je dobře kvazi objednanénebo krátce wqo.

Pro naše účely, a přechodový systém je struktura ${ displaystyle { mathcal {S}} = langle S, rightarrow, cdots rangle}$, kde ${ displaystyle S}$ je libovolná množina (její prvky se nazývají státy), a ${ displaystyle rightarrow subseteq S krát S}$ (jeho prvky se nazývají přechody). Obecně může přechodový systém mít další strukturu, jako jsou počáteční stavy, štítky přechodů, přijímající stavy atd. (Označené tečkami), ale zde se nás netýkají.

A dobře strukturovaný přechodový systém sestává z přechodového systému ${ displaystyle langle S, to, leq rangle}$, takový, že

• ${ displaystyle leq subseteq S krát S}$ je dobře kvazi-objednávka na množině států.
• ${ displaystyle leq}$ je nahoru kompatibilní s ${ displaystyle to}$: to znamená pro všechny přechody ${ displaystyle s_ {1} to s_ {2}}$ (tím myslíme ${ displaystyle (s_ {1}, s_ {2}) in to}$) a pro všechny ${ displaystyle t_ {1}}$ takhle ${ displaystyle s_ {1} leq t_ {1}}$, tady existuje ${ displaystyle t_ {2}}$ takhle ${ displaystyle t_ {1} { xrightarrow {*}} t_ {2}}$ (to znamená, ${ displaystyle t_ {2}}$ lze dosáhnout z ${ displaystyle t_ {1}}$ posloupností nulových nebo více přechodů) a ${ displaystyle s_ {2} leq t_ {2}}$.

Požadavek vzestupné kompatibility

Dobře strukturované systémy

A dobře strukturovaný systém^[1] je přechodový systém ${ displaystyle (S, to)}$ se stavovou sadou ${ displaystyle S = Q krát D}$ složený z konečného kontrolní stav soubor ${ displaystyle Q}$, a datové hodnoty soubor ${ displaystyle D}$, vybavené a rozhodnutelné předobjednávka ${ displaystyle leq subseteq D krát D}$ který je rozšířen na státy do ${ displaystyle (q, d) leq (q ', d') levá šipka q = q ' klín d leq d'}$, který je dobře strukturovaný, jak je definováno výše (${ displaystyle to}$ je monotónní, tj. vzestupně kompatibilní s ohledem na ${ displaystyle leq}$) a navíc má a vypočitatelný sada minim pro sadu předchůdců libovolného nahoru zavřeno podmnožina ${ displaystyle S}$.

Dobře strukturované systémy přizpůsobují teorii dobře strukturovaných přechodových systémů pro modelování určitých tříd systémů, se kterými se setkáváme počítačová věda a poskytnout základ pro rozhodovací postupy k analýze těchto systémů, a tedy i doplňkové požadavky: samotná definice WSTS neříká nic o vypočítatelnosti vztahů ${ displaystyle leq}$, ${ displaystyle to}$.

Využití v informatice

Dobře strukturované systémy

Pokrytí může být rozhodnuto pro jakýkoli dobře strukturovaný systém, a tak může dosáhnout dosažitelnost daného stavu kontroly zpětný algoritmus Abdulla a kol.^[1] nebo pro specifické podtřídy dobře strukturovaných systémů (s výhradou přísné monotónnosti,^[2] např. v případě neomezeného Petriho sítě ) dopřednou analýzou založenou na Karp-Miller pokrytí graf.

Zpětný algoritmus

Zpětný algoritmus umožňuje odpovědět na následující otázku: vzhledem k dobře strukturovanému systému a stavu ${ displaystyle s}$, existuje nějaká přechodová cesta, která vede z daného počátečního stavu ${ displaystyle s_ {0}}$ do stavu ${ displaystyle s ' geq s}$ (takový stav se říká Pokrýt ${ displaystyle s}$)?

Intuitivní vysvětlení této otázky zní: pokud ${ displaystyle s}$ představuje chybový stav, pak libovolný stav obsahující mělo by to být také považováno za chybový stav. Pokud lze najít dobře kvazi-řád, který modeluje toto „zadržování“ stavů a ​​který také splňuje požadavek monotónnosti s ohledem na přechodový vztah, pak lze na tuto otázku odpovědět.

Místo jednoho minimálního chybového stavu ${ displaystyle s}$, obvykle se uvažuje vzhůru uzavřená množina ${ displaystyle S_ {e}}$ chybových stavů.

Algoritmus je založen na faktech, které jsou v dobře kvazi-pořadí ${ displaystyle (A, leq)}$, každá vzhůru uzavřená množina má konečnou množinu minim a libovolnou sekvenci ${ displaystyle S_ {1} subseteq S_ {2} subseteq ...}$ vzestupně uzavřených podmnožin ${ displaystyle A}$ konverguje po konečně mnoha krocích (1).

Algoritmus musí ukládat vzhůru uzavřenou množinu ${ displaystyle S_ {s}}$ stavů v paměti, které může dělat, protože vzhůru uzavřená množina je reprezentovatelná jako konečná množina minim. Začíná to od uzavření sady chybových stavů směrem nahoru ${ displaystyle S_ {e}}$ a počítá při každé iteraci (podle monotónnosti také vzhůru zavřené) množinu bezprostředních předchůdců a její přidání do množiny ${ displaystyle S_ {s}}$. Tato iterace končí po konečném počtu kroků kvůli vlastnosti (1) dobře kvazi-objednávek. Li ${ displaystyle s_ {0}}$ je v sadě konečně získán, pak je výstup "ano" (stav ${ displaystyle S_ {e}}$ lze dosáhnout), jinak je „ne“ (do takového stavu není možné dosáhnout).

Reference