Bigraph - Bigraph - Wikipedia

Tento článek je o formalismu pro všudypřítomné výpočty. Grafy, jejichž hrany se střídají mezi dvěma druhy vrcholů, viz Bipartitní graf.

A bigraf (často se používá v množném čísle bigrafy) lze modelovat jako superpozici a graf (dále jen linkový graf) a soubor stromy (dále jen graf místa).[1][2]

Každý uzel bigraphu je součástí grafu a také součástí nějakého stromu, který popisuje, jak jsou uzly vnořeny. Bigraphs lze pohodlně a formálně zobrazit jako diagramy.[1] Mají aplikace v modelování distribuovaných systémů pro všudypřítomné výpočty a lze je použít k popisu mobilní, pohybliví interakce. Byly také používány Robin Milner ve snaze zahrnout Počet komunikačních systémů (CCS) a π-počet.[2] Byly studovány v kontextu teorie kategorií.[3]

Anatomie bigrafu

Kromě uzlů a (hyper- )hrany, bigraf může mít s ním spojenou jednu nebo více regionech což jsou kořeny v místním lese a nula nebo více díry v místním grafu, do kterého mohou být vloženy další oblasti bigrafu. Podobně uzlům můžeme přiřadit řízení které definují identity a arity (počet porty pro daný uzel, ke kterému se mohou spojovat hrany linkového grafu). Tyto ovládací prvky jsou čerpány z bigrafu podpis. V grafu propojení definujeme vnitřní a vnější názvy, které definují spojovací body, ve kterých mohou být shodné názvy spojeny do jednoho odkazu.

Nadace

Bigraph je n-tice:

kde je sada uzlů, je sada hran, je kontrolní mapa který přiřazuje ovládací prvky uzlům, je nadřazená mapa který definuje vnoření uzlů a je mapa odkazů který definuje strukturu odkazu.

Zápis označuje, že bigraf má díry (stránky) a soubor vnitřních jmen a regionechse sadou vnější jména . Tito jsou známí jako vnitřní a vnější rozhraní bigrafu.

Formálně vzato, každý bigraf je šipka v symetrické části monoidní kategorie (obvykle zkráceno kategorie spm), ve kterém jsou objekty těmito rozhraními.[4] Výsledkem je, že složení bigrafů je definovatelné, pokud jde o složení šipek v kategorii.

Rozšíření a varianty

Bigraphs se sdílením

Příklad bigrafu se sdílením
Příklad bigrafu se sdílením, ve kterém je uzel řízení M sdílen dvěma uzly řízení S. Toto je reprezentováno tím, že M je v průsečíku dvou S-uzlů.

Bigraphs se sdílením[5] jsou zevšeobecněním Milnerova formalizace, která umožňuje přímou reprezentaci překrývajících se nebo protínajících se prostorových umístění. Ve bigrafech se sdílením je graf místa definován jako a směrovaný acyklický graf (DAG), tj. je binární relace místo a mapa. Definice spojovacího grafu není zavedením sdílení nijak ovlivněna. Všimněte si, že standardní bigrafy jsou podtřídou bigrafů se sdílením.

Mezi oblasti použití bigrafů se sdílením patří bezdrátové síťové protokoly,[6] správa domácích bezdrátových sítí v reálném čase[7] a smíšená realita systémy.[8]

Implementace

  • BigraphER je prostředí pro modelování a uvažování pro bigrafy skládající se z OCaml knihovna a nástroj příkazového řádku poskytující efektivní implementaci přepisování, simulace a vizualizace pro bigrafy i bigrafy se sdílením.[9]

Viz také

Bibliografie

  • Milner, Robin (2009). Prostor a pohyb komunikujících agentů. Cambridge University Press. ISBN  978-0521738330.
  • Milner, Robin (2001). "Bigrafické reaktivní systémy, (pozvaný referát)". CONCUR 2001 - Teorie souběžnosti, Proc. 12. mezinárodní konference. Přednášky z informatiky. 2154. Springer-Verlag. 16–35. doi:10.1007/3-540-44685-0_2.
  • Milner, Robin (2002). "Bigraphs jako model pro mobilní interakci (pozvaný referát)". ICGT 2002: První mezinárodní konference o transformaci grafů. Přednášky z informatiky. 2505. Springer-Verlag. s. 8–13. doi:10.1007/3-540-45832-8_3.
  • Debois, Søren; Damgaard, Troels Christoffer (2005). "Bigrafy příkladem". Řada technických zpráv IT University TR-2005-61. Dánsko: IT univerzita v Kodani. CiteSeerX  10.1.1.73.176. ISBN  978-87-7949-090-1.
  • Sevegnani, Michele; Calder, Muffy (2015). „Bigraphs with sharing“. Teoretická informatika. 577: 43–73. doi:10.1016 / j.tcs.2015.02.011.

Reference

  1. ^ A b Stručný úvod k bigrafům, IT univerzita v Kodani, Dánsko.
  2. ^ A b Milner, Robin. Bigrafický model, Počítačová laboratoř University of Cambridge, SPOJENÉ KRÁLOVSTVÍ.
  3. ^ Milner, Robin (2008). „Bigrafy a jejich algebra“ (PDF). Elektronické poznámky v teoretické informatice. 209: 5–19. doi:10.1016 / j.entcs.2008.04.002.
  4. ^ Milner, Robin (2009). "Bigrafické kategorie". CONCUR 2009 - Teorie souběžnosti. Přednášky z informatiky. 5710. Springer-Verlag. 30–36. doi:10.1007/978-3-642-04081-8_3.
  5. ^ Sevegnani, Michele; Calder, Muffy (2015). „Bigraphs with sharing“. Teoretická informatika. 577: 43–73. doi:10.1016 / j.tcs.2015.02.011.
  6. ^ Calder, Muffy; Sevegnani, Michele (2014). „Modelování IEEE 802.11 CSMA / CA RTS / CTS se stochastickými bigrafy se sdílením“. Formální aspekty práce na počítači. 26 (3): 537–561. doi:10.1007 / s00165-012-0270-3.
  7. ^ Calder, Muffy; Koliousis, Alexandros; Sevegnani, Michele; Sventek, Joseph (2014). „Ověření bezdrátových domácích sítí v reálném čase pomocí bigrafů se sdílením“. Věda o počítačovém programování. 80: 288–310. doi:10.1016 / j.scico.2013.08.004.
  8. ^ Benford, Steve; Calder, Muffy; Rodden, Tom; Sevegnani, Michele (01.05.2016). „On Lions, Impala a Bigraphs: Modeling Interaction in Physical / Virtual Spaces“ (PDF). ACM Trans. Comput.-Hum. Interakce. 23 (2): 9:1–9:56. doi:10.1145/2882784. ISSN  1073-0516.
  9. ^ Sevegnani, Michele; Calder, Muffy (2016-07-17). Chaudhuri, Swarat; Farzan, Azadeh (eds.). Ověření pomocí počítače (PDF). Přednášky z informatiky. Springer International Publishing. 494–501. doi:10.1007/978-3-319-41540-6_27. ISBN  9783319415390.

externí odkazy