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
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
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 .