Bisimülasyon - Bisimulation

Olarak teorik bilgisayar biliminin bir ele almıştır a, ikili bir ilişki durum arasındaki geçiş sistemleri bu bir sistem aynı şekilde davranır tersi diğer ve yardımcısı taklit eden sistemleri birleştirilmesi.

Sezgisel olarak iki sistem, onları bazı kurallara göre bir oyun oynadıklarını varsayarsak , birbirlerinin hareketlerini eşleştiriyorlarsa , ikiye benziyorlar . Bu anlamda, sistemlerin her biri bir gözlemci tarafından birbirinden ayırt edilemez.

Resmi tanımlama

Etiketli bir durum geçiş sistemi verildiğinde ( ,, →), burada bir dizi durum, bir etiket kümesidir ve → bir etiketlenmiş geçişler kümesidir (yani, bir alt kümesi ), bir ikiye bölme bir ikili ilişkidir , öyle ki her ikisi de ve tersi olan simülasyonlar . Bundan, bir bisimülasyonun simetrik kapanmasının bir bisimülasyon olduğu ve her simetrik simülasyonun bir bisimülasyon olduğu anlaşılmaktadır. Bu nedenle bazı yazarlar bisimülasyonu simetrik bir simülasyon olarak tanımlamaktadır. ${\ displaystyle S}$ ${\ displaystyle \ Lambda}$ ${\ displaystyle S}$ ${\ displaystyle \ Lambda}$ ${\ displaystyle S \ times \ Lambda \ times S}$ ${\ displaystyle R \ subseteq S \ times S}$ ${\ displaystyle R}$ ${\ displaystyle R ^ {T}}$

Eşdeğer, bir olduğunu ele almıştır IFF durumlarının her çifti için de içinde a ve tüm etiketler : ${\ displaystyle R}$ ${\ displaystyle (p, q)}$ ${\ displaystyle R}$ ${\ displaystyle \ Lambda}$

eğer , o zaman öyle var ${\ displaystyle p {\ taşması {\ alpha} {\ rightarrow}} p '}$ ${\ displaystyle q {\ taşan {\ alpha} {\ rightarrow}} q '}$ ${\ displaystyle (p ', q') \ R içinde}$ ;

eğer , o zaman öyle var ${\ displaystyle q {\ taşan {\ alpha} {\ rightarrow}} q '}$ ${\ displaystyle p {\ taşması {\ alpha} {\ rightarrow}} p '}$ ${\ displaystyle (p ', q') \ R içinde}$ .

İki devlet Verilen ve içinde , bir bisimilar için yazılı, bir ele almıştır var IFF, öyle . Bu, iki benzerlik ilişkisinin tüm bisimülasyonların birleşimi olduğu anlamına gelir : tam olarak bir miktar bisimülasyon için . ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle S}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle p \, \ sim \, q}$ ${\ displaystyle R}$ ${\ displaystyle (p, q) \ R’de}$ ${\ displaystyle \, \ sim \,}$ ${\ displaystyle (p, q) \ in \, \ sim \,}$ ${\ displaystyle (p, q) \ R’de}$ ${\ displaystyle R}$

İkiye bölünme seti birleşme altında kapalıdır; bu nedenle, iki benzerlik ilişkisinin kendisi bir ikiye bölünmedir. Tüm bisimülasyonların birliği olduğu için, benzersiz en büyük bisimülasyondur. Bisimülasyonlar ayrıca refleksif, simetrik ve geçişli kapanma altında kapalıdır; bu nedenle, en büyük bisimülasyon, dönüşlü, simetrik ve geçişli olmalıdır. Bundan, en büyük bisimülasyonun - iki benzerliğin - bir eşdeğerlik ilişkisi olduğu sonucu çıkar .

Simüle ederse ve simüle ederse, bunların iki benzer olmasının her zaman geçerli olmadığını unutmayın. İçin ve bisimilar olmak arasındaki simülasyon ve olmalıdır tersi arasındaki simülasyon ve . Karşı örnek içinde CCS : ve birbirlerini taklit ama bisimilar değildir. ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle \, M = a.b + a \,}$ ${\ displaystyle \, M '= ab \}$

Alternatif tanımlar

İlişkisel tanım

Bisimülasyon, ilişkilerin bileşimi açısından aşağıdaki gibi tanımlanabilir .

Bir verilen etiketli durum geçiş sistemi , bir ele almıştır ilişki a, ikili bir ilişki içinde (diğer bir deyişle, ⊆ x o) gibi ${\ displaystyle (S, \ Lambda, \ rightarrow)}$ ${\ displaystyle R}$ ${\ displaystyle S}$ ${\ displaystyle R}$ ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle \ forall \ alpha \ in \ Lambda}$

{\ displaystyle R \; \ {\ taşan {\ alpha} {\ rightarrow}} \ quad {\ subseteq} \ quad {\ taşan {\ alpha} {\ rightarrow}} \; \ R}

ve

{\ displaystyle R ^ {- 1} \; \ {\ taşan {\ alfa} {\ rightarrow}} \ quad {\ subseteq} \ quad {\ taşan {\ alpha} {\ rightarrow}} \; \ R ^ { -1}}

İlişki kompozisyonunun monotonluğundan ve sürekliliğinden, bisimülasyonlar kümesinin birlikler altında kapatıldığı (ilişkiler kümesinde birleştiği) ve basit bir cebirsel hesaplama, iki benzerlik ilişkisinin - tüm bisimülasyonların birleşimi - olduğunu gösterir. bir denklik ilişkisi. Bu tanım ve ilişkili iki benzerlik tedavisi, herhangi bir kapsayıcı nicelikle yorumlanabilir .

Sabit nokta tanımı

İki benzerlik, teorik olarak, sabit nokta teorisi açısından , daha kesin olarak aşağıda tanımlanan belirli bir fonksiyonun en büyük sabit noktası olarak da tanımlanabilir.

Etiketli bir durum geçiş sistemi verildiğinde ( , Λ, →), aşağıdaki gibi ikili ilişkilerden ikili ilişkilere kadar bir fonksiyon olarak tanımlayın: ${\ displaystyle S}$ ${\ displaystyle F: {\ mathcal {P}} (S \ times S) \ - {\ mathcal {P}} (S \ times S)}$ ${\ displaystyle S}$ ${\ displaystyle S}$

Herhangi bir ikili ilişki olalım . × ' deki tüm çiftlerin kümesi olarak tanımlanır, öyle ki: ${\ displaystyle R}$ ${\ displaystyle S}$ ${\ displaystyle F (R)}$ ${\ displaystyle (p, q)}$ ${\ displaystyle S}$ ${\ displaystyle S}$

{\ displaystyle \ forall \ alpha \ in \ Lambda. \, \ forall p '\ in S. \, p {\ taşması {\ alpha} {\ rightarrow}} p' \, \ Rightarrow \, \ q '\ var S. \, q {\ overset {\ alpha} {\ rightarrow}} q '\, {\ textrm {ve}} \, (p', q ') \ içinde R}

ve

{\ displaystyle \ forall \ alpha \ in \ Lambda. \, \ forall q '\ in S. \, q {\ taşan {\ alpha} {\ rightarrow}} q' \, \ Rightarrow \, \ var p '\ S. \, p {\ taşması {\ alpha} {\ rightarrow}} p '\, {\ textrm {ve}} \, (p', q ') \ içinde R}

Daha sonra iki benzerlik, en büyük sabit nokta olarak tanımlanır . ${\ displaystyle F}$

Ehrenfeucht – Fraïssé oyun tanımı

Bisimülasyon, iki oyuncu arasındaki bir oyun olarak da düşünülebilir: saldıran ve savunan.

"Saldırgan" ilk gider ve, herhangi bir geçerli geçişi seçebilir gelen . Yani: ${\ displaystyle \ alpha}$ ${\ displaystyle (p, q)}$

${\ displaystyle (p, q) {\ taşan {\ alfa} {\ rightarrow}} (p ', q)}$ veya ${\ displaystyle (p, q) {\ taşan {\ alfa} {\ rightarrow}} (p, q ')}$

"Defender" o zaman, bu geçişi maç için çalışmalıdır birinden veya saldırganın hareket bağlı. Yani, öyle bir şey bulmalılar : ${\ displaystyle \ alpha}$ ${\ displaystyle (p ', q)}$ ${\ displaystyle (p, q ')}$ ${\ displaystyle \ alpha}$

${\ displaystyle (p ', q) {\ taşan {\ alpha} {\ rightarrow}} (p', q ')}$ veya ${\ displaystyle (p, q ') {\ taşan {\ alpha} {\ rightarrow}} (p', q ')}$

Hücum oyuncusu ve savunma oyuncusu, aşağıdakilere kadar dönüşümlü sıralar almaya devam eder:

Savunan, saldırganın hareketine uygun herhangi bir geçerli geçiş bulamaz. Bu durumda saldırgan kazanır.
Oyun , her ikisi de 'ölü' olan durumlara ulaşır (yani, her iki durumda da geçiş yoktur) Bu durumda, savunma oyuncusu kazanır. ${\ displaystyle (p, q)}$
Oyun sonsuza kadar devam eder ve bu durumda savunma oyuncusu kazanır.
Oyun , daha önce ziyaret edilmiş durumlara ulaşır . Bu, sonsuz bir oyuna eşdeğerdir ve savunma oyuncusu için bir kazanç olarak kabul edilir. ${\ displaystyle (p, q)}$

Yukarıdaki tanıma göre sistem, ancak ve ancak savunmacı için kazanan bir strateji varsa bir ikiye bölünmedir.

Kömürsel tanım

Durum geçiş sistemleri için ele almıştır özel bir durumu olan coalgebraic bildirdiğinden Powerset türü için ele almıştır funktor . Her durum geçiş sistemi olup, Not olan bijectively bir işlev gelen için POWERSET arasında endeksli olarak yazılı tarafından tanımlanan ${\ displaystyle (S, \ Lambda, \ rightarrow)}$ ${\ displaystyle \ xi _ {\ rightarrow}}$ ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle \ Lambda}$ ${\ displaystyle {\ mathcal {P}} (\ Lambda \ times S)}$

{\ displaystyle p \ mapsto \ {(\ alpha, q) \ in \ Lambda \ times S: p {\ taşan {\ alpha} {\ rightarrow}} q \}.}

Let be -th projeksiyon haritalama için ve sırasıyla ; ve üçüncü bileşeni bırakarak tanımlanan ileri imajı ${\ displaystyle \ pi _ {i} \ iki nokta üst üste S \ çarpı S \ ila S}$ ${\ displaystyle i}$ ${\ displaystyle (p, q)}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle i = 1,2}$ ${\ displaystyle {\ mathcal {P}} (\ Lambda \ times \ pi _ {1})}$ ${\ displaystyle \ pi _ {1}}$

{\ displaystyle P \ mapsto \ {(\ alpha, p) \ in \ Lambda \ times S: \ var q. (\ alpha, p, q) \ P \}}

alt kümesi nerede . Benzer şekilde . ${\ displaystyle P}$ ${\ displaystyle \ Lambda \ times S \ times S}$ ${\ displaystyle {\ mathcal {P}} (\ Lambda \ times \ pi _ {2})}$

Yukarıdaki açıklamalar kullanılarak, bir ilişkinin a, ele almıştır bir geçiş sistemi üzerinde bir geçiş sistemini vardır, ancak ve ancak ilişkisi üzerinde böyle şeması ${\ displaystyle R \ subseteq S \ times S}$ ${\ displaystyle (S, \ Lambda, \ rightarrow)}$ ${\ displaystyle \ gamma \ iki nokta üst üste R \ - {\ mathcal {P}} (\ Lambda \ times R)}$ ${\ displaystyle R}$

işe gidip gelme, yani denklemler için ${\ displaystyle i = 1,2}$

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

işlevsel temsilinin nerede olduğunu tutun . ${\ displaystyle \ xi _ {\ rightarrow}}$ ${\ displaystyle (S, \ Lambda, \ rightarrow)}$

Bisimülasyon çeşitleri

Özel bağlamlarda, bisimülasyon kavramı bazen ek gereksinimler veya kısıtlamalar eklenerek rafine edilir. Bir örnek, ara durumların başlangıç durumuna ("kekemeler") eşdeğer olması koşuluyla, bir sistemin bir geçişinin diğerinin çoklu geçişleriyle eşleştirilebildiği kekemelik bisimülasyonudur .

Durum geçiş sistemi , genellikle ile belirtilen sessiz (veya iç ) eylem kavramını içeriyorsa , yani dış gözlemciler tarafından görülemeyen eylemler, bisimülasyon zayıf bisimülasyon olarak gevşetilebilir , burada iki durum ve bisimilar ve önde gelen iç işlemlerden bir sayı olduğu bir duruma daha sonra halinde de mevcut olmalıdır önde gelen iç işlemlerden bazılarını numarası (sıfır olabilir) olduğu şekilde hiç . Bir ilişki aşağıdakine sahip ile (eğer süreçlere zayıf ele almıştır olan ve sırasıyla bir gözlenebilir ve kapatma geçiş olmak üzere): ${\ displaystyle \ tau}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle p '}$ ${\ displaystyle q '}$ ${\ displaystyle q}$ ${\ displaystyle q '}$ ${\ displaystyle {\ mathcal {R}}}$ ${\ displaystyle {\ mathcal {S}} \ in \ {{\ mathcal {R}}, {\ mathcal {R}} ^ {- 1} \}}$ ${\ displaystyle a, \ tau}$

${\ displaystyle \ forall p, q. \ quad (p, q) \ içinde {\ mathcal {S}} \ Rightarrow p {\ stackrel {\ tau} {\ rightarrow}} p '\ Rightarrow \ var q'. \ dörtlü q {\ stackrel {\ tau ^ {\ ast}} {\ rightarrow}} q '\ wedge (p', q ') \ içinde {\ mathcal {S}}}$

${\ displaystyle \ forall p, q. \ quad (p, q) \ içinde {\ mathcal {S}} \ Rightarrow p {\ stackrel {a} {\ rightarrow}} p '\ Rightarrow \ var q'. \ quad q {\ stackrel {\ tau ^ {\ ast} a \ tau ^ {\ ast}} {\ rightarrow}} q '\ wedge (p', q ') \ {\ mathcal {S}}} içinde$

Bu, bir ilişkiye kadar bisimülasyon ile yakından ilgilidir .

Genellikle, durum geçiş sistemi veren işletme semantik a programlama dilinde , daha sonra ele almıştır kesin tanımı programlama dili kısıtlama özgü olacaktır. Bu nedenle, genel olarak, bağlama bağlı olarak birden fazla türde bisimülasyon (bisimilarity veya bisimilarity) ilişki olabilir.

Çift simülasyon ve modal mantık

Yana Kripke modelleri (etiketli) durum geçiş sistemlerinin özel bir durum vardır, ele almıştır ayrıca bir konudur modal mantık . Aslında modal mantık, bisimülasyon altındaki birinci dereceden mantıksal değişmezin parçasıdır ( van Benthem teoremi ).

Algoritma

Polinom zamanında iki sonlu geçiş sisteminin iki benzer olup olmadığının kontrol edilmesi yapılabilir. En hızlı algoritmalar, en kaba bölümleme problemine indirgeme yoluyla bölüm iyileştirmeyi kullanan doğrusal zamandır .

Ayrıca bakınız

Referanslar

daha fazla okuma

Park, David (1981). "Sonsuz Dizilerde Eşzamanlılık ve Otomata". Deussen'de, Peter (ed.). Teorik Bilgisayar Bilimleri . 5. GI-Konferansı Bildirileri, Karlsruhe. Bilgisayar Bilimleri Ders Notları . 104 . Springer-Verlag . s. 167–183. doi : 10.1007 / BFb0017309 . ISBN 978-3-540-10576-3 .
Milner, Robin (1989). İletişim ve Eşzamanlılık . Prentice Hall . ISBN 0-13-114984-9 .
Davide Sangiorgi. (2011). Bisimülasyon ve Koindüksiyona Giriş . Cambridge University Press. Mayıs ISBN 9781107003637

Dış bağlantılar

Yazılım araçları

CADP : çeşitli bisimülasyonlara göre sonlu durum sistemlerini en aza indirmek ve karşılaştırmak için araçlar
mCRL2 : çeşitli bisimülasyonlara göre sonlu durum sistemlerini en aza indirmek ve karşılaştırmak için araçlar
Bisimülasyon Oyunu Oyunu

Languages

In other projects