bigraf

Bigraf można modelować jako superpozycję grafu ( wykres łączący ) i zestawu drzew ( wykres miejsca ).

Każdy węzeł bigrafu jest częścią grafu, a także częścią jakiegoś drzewa opisującego sposób zagnieżdżenia węzłów. Bigrafy można wygodnie i formalnie przedstawić jako diagramy . Mają zastosowanie w modelowaniu systemów rozproszonych dla komputerów wszechobecnych i mogą być wykorzystywane do opisywania interakcji mobilnych . Zostały one również użyte przez Robina Milnera w próbie podporządkowania rachunku całkowego systemów komunikacyjnych (CCS) i rachunku π . Zostały one zbadane w kontekście teorii kategorii .

Anatomia bigrafu

Oprócz węzłów i ( hiper ) krawędzi , bigraf może mieć powiązany jeden lub więcej regionów , które są korzeniami w lesie miejsc i zero lub więcej dziur w grafie miejsca, w które można wstawić inne regiony bigrafu. Podobnie do węzłów możemy przypisać kontrolki , które definiują tożsamości i arność (liczbę portów dla danego węzła, do których mogą łączyć się krawędzie grafów łączących). Te elementy sterujące pochodzą z podpisu dwuznakowego . W grafie powiązań definiujemy wewnętrzne i zewnętrzne , które definiują punkty połączeń, w których zbieżne nazwy mogą być łączone w celu utworzenia pojedynczego łącza.

Podwaliny

Bigraf to krotka 5:

gdzie to węzłów, to , kontrolna która kontrole do węzłów to mapa nadrzędna , która definiuje zagnieżdżanie węzłów, a mapa która definiuje łączy

Notacja wskazuje, że bigraf ma dziury (miejsca) i zestaw nazw wewnętrznych regionów z zestawem nazw zewnętrznych { . Są one odpowiednio znane jako wewnętrzne i zewnętrzne interfejsy bigrafu.

Formalnie rzecz biorąc, każdy bigraf jest strzałką w symetrycznej częściowej kategorii monoidalnej (zwykle w skrócie spm-category ), w której obiektami są te interfejsy. W rezultacie kompozycja bigrafów jest definiowalna w kategoriach kompozycji strzałek w kategorii.

Rozszerzenia i warianty

Skierowany bigraf modelujący system kontenerowy.

Wyreżyserowane bigrafy

Bigrafy skierowane to uogólnienie bigrafów, w których hiper-krawędzie grafu łączącego są skierowane. Porty i nazwy interfejsów są rozszerzone o polaryzację (dodatnią lub ujemną) z zastrzeżeniem, że kierunek hiperkrawędzi przechodzi od ujemnego do dodatniego.

Ukierunkowane bigrafy zostały wprowadzone jako metamodel do opisywania paradygmatów obliczeniowych dotyczących lokalizacji i komunikacji zasobów, gdzie skierowany graf powiązań zapewnia naturalny opis zależności zasobów lub przepływu informacji. Przykładami obszarów zastosowań są protokoły bezpieczeństwa , zarządzanie dostępem do zasobów i przetwarzanie w chmurze .

Bigrafy z udostępnianiem

Example bigraph with sharing
Przykładowy bigraf ze współdzieleniem, w którym węzeł kontrolny M jest wspólny dla dwóch węzłów kontrolnych S. Jest to reprezentowane przez M znajdujące się na przecięciu dwóch S-węzłów.

Bigrafy ze współdzieleniem to uogólnienie formalizacji Milnera, które pozwala na prostą reprezentację nakładających się lub przecinających się lokalizacji przestrzennych. W jako wykres acykliczny (DAG) , tj jest relacją binarną mapy . Wprowadzenie udostępniania nie ma wpływu na definicję wykresu połączeń. Zauważ, że standardowe bigrafy są podklasą bigrafów z udostępnianiem.

Obszary zastosowania bigrafów z udostępnianiem obejmują protokoły sieci bezprzewodowych, zarządzanie domowymi sieciami bezprzewodowymi w czasie rzeczywistym oraz systemy rzeczywistości mieszanej .

Narzędzia i wdrożenia

  • BigraphER to środowisko do modelowania i wnioskowania dla bigrafów, składające się z biblioteki OCaml i narzędzia wiersza poleceń, zapewniającego wydajną implementację przepisywania, symulacji i wizualizacji zarówno bigrafów, jak i bigrafów z udostępnianiem.
  • jLibBig to biblioteka Java zapewniająca wydajną i rozszerzalną implementację bigraficznych systemów reaktywnych zarówno dla dwuznaków, jak i skierowanych bigrafów.

Nie jest już aktywnie rozwijany:

  • BigMC to narzędzie do sprawdzania modeli dla bigrafów, które zawiera interfejs wiersza poleceń i wizualizację.
  • Big Red to graficzny edytor bigrafów z łatwo rozszerzalną obsługą różnych formatów plików.
  • SBAM to stochastyczny symulator bigrafów, mający na celu symulację modeli biologicznych.
  • DBAM to rozproszony symulator bigraficznych systemów reaktywnych.
  • DBtk to zestaw narzędzi do skierowanych bigrafów, który zapewnia obliczanie IPO, dopasowywanie i wizualizację.


Zobacz też

Bibliografia

  •   Milner, Robin (2009). Przestrzeń i ruch agentów komunikujących się . Wydawnictwo Uniwersytetu Cambridge . ISBN 978-0521738330 .
  • Milner, Robin (2001). „Biograficzne systemy reaktywne (artykuł na zaproszenie)”. CONCUR 2001 – Teoria współbieżności, Proc. XII Międzynarodowa Konferencja . Notatki z wykładów z informatyki . Tom. 2154. Springer-Verlag . s. 16–35. doi : 10.1007/3-540-44685-0_2 .
  • Milner, Robin (2002). „Bigrafy jako model interakcji mobilnej (artykuł na zaproszenie)” . ICGT 2002: Pierwsza międzynarodowa konferencja na temat transformacji grafów . Notatki z wykładów z informatyki . Tom. 2505. Springer-Verlag. s. 8–13. doi : 10.1007/3-540-45832-8_3 .
  •    Debois, Søren; Damgaard, Troels Christoffer (2005). „Bigrafy według przykładu”. Seria raportów technicznych uniwersytetów IT TR-2005-61 . Dania: Uniwersytet IT w Kopenhadze . CiteSeerX 10.1.1.73.176 . ISBN 978-87-7949-090-1 .
  • Sevegnani, Michele; Calder, Muffy (2015). „Bigrafy z udostępnianiem” . Informatyka teoretyczna . 577 : 43–73. doi : 10.1016/j.tcs.2015.02.011 .

Linki zewnętrzne