Bisimulace - Bisimulation

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Bisimulace“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Února 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teoretická informatika A bisimulace je binární relace mezi státní přechodové systémy, sdružující systémy, které se chovají stejným způsobem v tom smyslu, že jeden systém simuluje druhý a naopak.

Intuitivně jsou to dva systémy bisimilar pokud si navzájem odpovídají pohyby. V tomto smyslu nemůže být každý ze systémů odlišen od druhého pozorovatelem.

Formální definice

Vzhledem k označený stavový přechodový systém (${ displaystyle S}$, ${ displaystyle Lambda}$, →), kde ${ displaystyle S}$ je sada států, ${ displaystyle Lambda}$ je sada štítků a → je sada označených přechodů (tj. podmnožina ${ displaystyle S}$ × ${ displaystyle Lambda}$ × ${ displaystyle S}$), a bisimulace vztah je binární relace ${ displaystyle R}$ přes ${ displaystyle S}$ (tj., ${ displaystyle R}$ ⊆ ${ displaystyle S}$ × ${ displaystyle S}$) takové, že oba ${ displaystyle R}$ a jeho konverzovat ${ displaystyle R ^ {T}}$ jsou simulace.

Ekvivalentně ${ displaystyle R}$ je bisimulace, pokud pro každou dvojici prvků ${ displaystyle p, q}$ v ${ displaystyle S}$ s ${ displaystyle (p, q)}$ v ${ displaystyle R}$, pro všechny α in ${ displaystyle Lambda}$:

pro všechny ${ displaystyle p '}$ v ${ displaystyle S}$,

${ displaystyle p { overset { alpha} { rightarrow}} p '}$

znamená, že existuje ${ displaystyle q '}$ v ${ displaystyle S}$ takhle

${ displaystyle q { overset { alpha} { rightarrow}} q '}$

a ${ displaystyle (p ', q') v R}$;

a symetricky pro všechny ${ displaystyle q '}$ v ${ displaystyle S}$

${ displaystyle q { overset { alpha} { rightarrow}} q '}$

znamená, že existuje ${ displaystyle p '}$ v ${ displaystyle S}$ takhle

${ displaystyle p { overset { alpha} { rightarrow}} p '}$

a ${ displaystyle (p ', q') v R}$.

Vzhledem k tomu, dva státy ${ displaystyle p}$ a ${ displaystyle q}$ v ${ displaystyle S}$, ${ displaystyle p}$ je bisimilar na ${ displaystyle q}$, psaný ${ Displaystyle p , sim , q}$, pokud existuje bisimulace ${ displaystyle R}$ takhle ${ displaystyle (p, q)}$ je v ${ displaystyle R}$.

Vztah bisimilarity ${ displaystyle , sim ,}$ je vztah ekvivalence. Dále se jedná o největší bisimulační vztah v daném přechodovém systému.

Všimněte si, že ne vždy platí, že pokud ${ displaystyle p}$ simuluje ${ displaystyle q}$ a ${ displaystyle q}$ simuluje ${ displaystyle p}$ pak jsou bisimilární. Pro ${ displaystyle p}$ a ${ displaystyle q}$ simulace mezi ${ displaystyle p}$ a ${ displaystyle q}$ musí být konverzovat simulace mezi ${ displaystyle q}$ a ${ displaystyle p}$. Protiklad (v CCS, popisující kávovar): ${ displaystyle M = p. { overline {c}}. M + p. { overline {t}}. M + p. ({ overline {c}}. M + { overline {t}}. M )}$ a ${ displaystyle M '= p. ({ overline {c}}. M' + { overline {t}}. M ')}$ navzájem se simulují, ale nejsou si podobní.

Alternativní definice

Relační definice

Bisimulaci lze definovat z hlediska složení vztahů jak následuje.

Vzhledem k označený stavový přechodový systém ${ displaystyle (S, Lambda, rightarrow)}$, a bisimulace vztah je binární relace ${ displaystyle R}$ přes ${ displaystyle S}$ (tj., ${ displaystyle R}$ ⊆ ${ displaystyle S}$ × ${ displaystyle S}$) takové, že ${ displaystyle forall alpha in Lambda}$

${ displaystyle R ; { přesahující { alpha} { rightarrow}} quad { subseteq} quad { overset { alpha} { rightarrow}} ; R}$

a

${ displaystyle R ^ {- 1} ; { přesahující { alpha} { rightarrow}} quad { subseteq} quad { overset { alpha} { rightarrow}} ; R ^ { -1}}$

Z monotónnosti a kontinuity kompozice vztahů okamžitě vyplývá, že množina bisimulací je uzavřena pod odbory (spojení v posetu vztahů) a jednoduchý algebraický výpočet ukazuje, že vztah bisimilarity - spojení všech bisimulací - je vztah ekvivalence. Tuto definici as ní spojenou léčbu bisimilarity lze interpretovat v jakémkoli involutivu kvantale.

Definice fixního bodu

Bisimilarity lze definovat také v objednávat teoreticky móda, pokud jde o teorie pevných bodů, přesněji jako největší pevný bod určité funkce definované níže.

Vzhledem k označený stavový přechodový systém (${ displaystyle S}$, Λ, →), definovat ${ displaystyle F: { mathcal {P}} (S krát S) až { mathcal {P}} (S krát S)}$ být funkcí z binárních vztahů ${ displaystyle S}$ k binárním vztahům ${ displaystyle S}$, jak následuje:

Nechat ${ displaystyle R}$ být libovolným binárním vztahem ${ displaystyle S}$. ${ displaystyle F (R)}$ je definována jako množina všech párů ${ displaystyle (p, q)}$ v ${ displaystyle S}$ × ${ displaystyle S}$ takové, že:

${ displaystyle forall alpha in Lambda. , forall p ' in S. , p { overet { alpha} { rightarrow}} p' , Rightarrow , existuje q ' v S. , q { overset { alpha} { rightarrow}} q ', { textrm {and}} , (p', q ') v R}$

a

${ displaystyle forall alpha in Lambda. , forall q ' in S. , q { overet { alpha} { rightarrow}} q' , Rightarrow , existuje p ' v S. , p { overset { alpha} { rightarrow}} p ', { textrm {and}} , (p', q ') v R}$

Bisimilarity je pak definována jako největší pevný bod z ${ displaystyle F}$.

Teoretická definice hry

Bisimulaci lze také považovat za hru dvou hráčů: útočníka a obránce.

„Útočník“ jde jako první a může zvolit jakýkoli platný přechod, ${ displaystyle alpha}$, z ${ displaystyle (p, q)}$. Tj.:

${ displaystyle (p, q) { přesahující { alpha} { rightarrow}} (p ', q)}$nebo ${ displaystyle (p, q) { přesahující { alpha} { rightarrow}} (p, q ')}$

„Obránce“ se pak musí pokusit tento přechod přizpůsobit, ${ displaystyle alpha}$ z obou ${ displaystyle (p ', q)}$ nebo ${ displaystyle (p, q ')}$ v závislosti na pohybu útočníka, tj. musí najít ${ displaystyle alpha}$ takové, že:

${ displaystyle (p ', q) { přesahující { alpha} { rightarrow}} (p', q ')}$nebo ${ displaystyle (p, q ') { přesahující { alpha} { rightarrow}} (p', q ')}$

Útočník a obránce pokračují ve střídání, dokud:

• Obránce není schopen najít žádné platné přechody, které by odpovídaly pohybu útočníka. V tomto případě útočník vyhraje.
• Hra dosáhne států ${ displaystyle (p, q)}$ které jsou oba „mrtvé“ (tj. neexistují žádné přechody z žádného státu). V tomto případě obránce vyhrává
• Hra pokračuje věčně, v takovém případě obránce vyhraje.
• Hra dosáhne států ${ displaystyle (p, q)}$, které již byly navštíveny. To je ekvivalent nekonečné hry a počítá se to jako výhra obránce.

Podle výše uvedené definice je systém bisimulací právě tehdy, pokud pro obránce existuje vítězná strategie.

Coalgebraická definice

Bisimulace pro systémy přechodu státu je zvláštním případem uhlíkatý bisimulace pro typ kovarianční sady sil funktor Všimněte si, že každý systém přechodu státu ${ displaystyle (S, Lambda, rightarrow)}$ je bijektivně funkce ${ displaystyle xi _ { rightarrow}}$ z ${ displaystyle S}$ do výkonová sada z ${ displaystyle S}$ indexováno podle ${ displaystyle Lambda}$ psáno jako ${ displaystyle { mathcal {P}} ( Lambda krát S)}$, definován

${ displaystyle p mapsto {( alpha, q) in Lambda krát S: p { overset { alpha} { rightarrow}} q }.}$

Nechat ${ displaystyle pi _ {i} dvojtečka S krát S až S}$ být ${ displaystyle i}$-th projekce mapování${ displaystyle (p, q)}$ na ${ displaystyle p}$ a ${ displaystyle q}$ respektive pro ${ displaystyle i = 1,2}$; a${ displaystyle { mathcal {P}} ( Lambda times pi _ {1})}$ přední obrázek ${ displaystyle pi _ {1}}$ definováno upuštěním třetí komponenty

${ Displaystyle P mapsto {( alfa, p) v lambda krát S: existuje q. ( alpha, p, q) v P }}$

kde ${ displaystyle P}$ je podmnožinou ${ displaystyle Lambda krát S krát S}$. Podobně pro ${ displaystyle { mathcal {P}} ( Lambda times pi _ {2})}$.

Pomocí výše uvedených notací vztah ${ displaystyle R subseteq S krát S}$ je bisimulace na přechodovém systému ${ displaystyle (S, Lambda, rightarrow)}$ pouze tehdy, pokud existuje přechodový systém ${ displaystyle gamma dvojtečka R až { mathcal {P}} ( Lambda krát R)}$ o vztahu ${ displaystyle R}$ takové, že diagram

dojíždění, tj. za ${ displaystyle i = 1,2}$, rovnice

${ displaystyle xi _ { rightarrow} circ pi _ {i} = { mathcal {P}} ( Lambda times pi _ {i}) circ gamma}$

kdekoli ${ displaystyle xi _ { rightarrow}}$ je funkční reprezentace ${ displaystyle (S, Lambda, rightarrow)}$.

Varianty bisimulace

Ve zvláštních kontextech je pojem bisimulace někdy vylepšen přidáním dalších požadavků nebo omezení. Příkladem je to koktání bisimulace, ve kterém může být jeden přechod jednoho systému spojen s více přechody druhého, za předpokladu, že mezilehlé stavy jsou ekvivalentní počátečnímu stavu („koktání“).^[1]

Jiná varianta platí, pokud systém přechodu stavu obsahuje pojem tichý (nebo vnitřní) akce, často označovaná ${ displaystyle tau}$, tj. akce, které nejsou viditelné externími pozorovateli, pak může být bisimulace uvolněná slabá bisimulace, ve kterém pokud dva státy ${ displaystyle p}$ a ${ displaystyle q}$ jsou podobná a existuje určitý počet vnitřních akcí vedoucích z ${ displaystyle p}$ do nějakého státu ${ displaystyle p '}$ pak musí existovat stav ${ displaystyle q '}$ takové, že existuje určitý počet (možná nula) vnitřních akcí vedoucích z ${ displaystyle q}$ na ${ displaystyle q '}$. Vztah ${ displaystyle { mathcal {R}}}$ u procesů je slabá bisimulace, pokud platí následující (s ${ displaystyle { mathcal {S}} in {{ mathcal {R}}, { mathcal {R}} ^ {- 1} }}$, a ${ displaystyle a, tau}$ pozorovatelný a tichý přechod):

${ displaystyle forall p, q. quad (p, q) v { mathcal {S}} Rightarrow p { stackrel { tau} { rightarrow}} p ' Rightarrow existuje q'. quad q { stackrel { tau ^ { ast}} { rightarrow}} q ' wedge (p', q ') in { mathcal {S}}}$

${ displaystyle forall p, q. quad (p, q) v { mathcal {S}} Rightarrow p { stackrel {a} { rightarrow}} p ' Rightarrow existuje q'. quad q { stackrel { tau ^ { ast} a tau ^ { ast}} { rightarrow}} q ' wedge (p', q ') in { mathcal {S}}}$

To úzce souvisí s bisimulací až do vztah.

Typicky, pokud státní přechodový systém dává operační sémantika a programovací jazyk, pak bude přesná definice bisimulace specifická pro omezení programovacího jazyka. Obecně tedy může existovat více než jeden druh bisimulace (vztah bisimilarity) v závislosti na kontextu.

Bisimulace a modální logika

Od té doby Modely Kripke jsou zvláštním případem (označených) stavových přechodových systémů, bisimulace je také tématem v modální logika. Ve skutečnosti je modální logika fragmentem logika prvního řádu invariantní pod bisimulací (van Benthemova věta ).

Algoritmus

Ověření, že dva konečné přechodové systémy jsou bimimilární, lze provést v polynomiálním čase.^[2]

Viz také

• Předobjednávka simulace
• Vztah shody
• Pravděpodobnostní bisimulace

Reference

Další čtení

• Park, David (1981). "Souběžnost a automaty v nekonečných sekvencích". V Deussen, Peter (ed.). Teoretická informatika. Sborník z 5. konference GI, Karlsruhe. Přednášky z informatiky. 104. Springer-Verlag. 167–183. doi:10.1007 / BFb0017309. ISBN  978-3-540-10576-3.
• Milner, Robin (1989). Komunikace a souběžnost. Prentice Hall. ISBN  0-13-114984-9.
• Davide Sangiorgi. (2011). Úvod do bisimulace a koindukce. Cambridge University Press. ISBN  9781107003637

externí odkazy

Softwarové nástroje

• CADP: nástroje k minimalizaci a porovnání systémů konečných stavů podle různých bisimulací
• mCRL2: nástroje k minimalizaci a porovnání systémů konečných stavů podle různých bisimulací
• Hra Bisimulation Game