《软件学报》《软件学报》软件学报Journal of Software1000-98251000-9825《软件学报》编辑部10.13328/j.cnki.jos.004939TP301理论计算机科学THEORETICAL COMPUTER SCIENCE偶图及其应用研究综述Survey on Bigraph and Its Applications许东*dxu@shu.edu.cn王晶晶李静XUDong*dxu@shu.edu.cnWANGJing-JingLIJing上海大学 计算机工程与科学学院, 上海 200444School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China许东(1968-),男,安徽芜湖人,博士,副教授,CCF 专业会员,主要研究领域为新型计算模型, E-mail: dxu@shu.edu.cn.王晶晶(1990-),女,硕士生,主要研究领域为新型计算模型.李静(1989-),女,硕士,主要研究领域为新型计算模型;25120162721952081701201421092014
Bigraph was proposed by Robin Milner in 2001 as a formal theoretical model based on graphs in attempt to provide a design, simulation and analysis platform for ubiquitous computing and present a unified, extensible framework for the existing process algebra. In this paper first introduces the basic concepts of bigraph and reveals relationships among precategory, category, s-category and symmetric partial monoidal category which form the mathematical basis of bigraph, and then summarizes bigraphical algebra system while providing a simplified representation of the discrete normal form in bigraph with a proof. Next, it discusses some questions related to the definition of bigraphical categories and quotient translations after making a survey of the development of bigraph and its applications. This study argues that bigraphical category should be small category other than large category. Moreover, the paper illustrates how to convert the large category derived by quotient to small category. Finally, it outlines the extensions of bigraphical models and their applications.
两个偶图F和G,如果忽略了它们的闲置边,它们是支持等价的,那么称F和G是瘦-支集等价的,写作FG.对于偶图的s-范畴$`BG\left( k \right)$它的瘦-支集商$BG\left( k \right)$${\mathop {\rm{ = }}\limits^{{\rm{def}}} }$$`BG\left( k \right)$/它的对象是$`BG\left( k \right)$的对象,箭头[G]:I→J,是$`BG\left( k \right)$中同态集(I→J)的瘦-支集等价类,BG(K)叫做抽象偶图.同时也定义了一个函子:
ReferencesMilnerRBigraphical reactive systems. In: Proc. of the 12th Int'l Conf. on Concurrency Theory20011635MilnerRA calculus of communicating systems. In: Lecture Notes in Computer Science198092MilnerRCommunicating and Mobile Systems: The p-Calculus1999CardelliLGordonADMobile ambients2000240177213MilnerRCalculi for interaction1996338707737SewellPFrom rewrite rules to bisimulation congruences20022741183230LeiferJJMilnerRDeriving bisimulation congruences for reactive systems. In: Proc. of the 11th Int'l Conf. on Concurrency Theory (CONCUR 2000)2000243258LeiferJOperational congruences for reactive systems2001CattaniGLLeiferJJMilnerRContexts and embeddings for closed shallowaction graphs2000SassoneVSobocinskiPDeriving bisimulation congruences: A 2-categorical approach2002682105123SassoneVSobocinskiPLocating reaction with 2-categories20053331297327KellyGMBasic concepts of enriched category theory. In: Proc. of the Republished (2005) in Theory and Applications of Categories 10.LNM 6419821136LawvereFWMetric spaces, generalized logic, and closed categories1973431135166EhrigHIntroduction to the algebraic theory of graph grammars. In: Proc. of the Graph Grammars and their Application to Computer Science and Biology1979169MeseguerJMontanariUPetri nets are monoids1990882105155BundgaardMSassoneVTyped polyadic pi-calculus in bigraphs. In: Proc. of the 8th ACM SIGPLAN Int'l Conf. on Principles and Practice of Declarative Programming2006112JensenOHMobile Processes in Bigraphs, 2006, http://www.cl.cam.ac.uk/~rm135/Jensen-monograph.htmlJensenOHMilnerRBigraphs and transitions. In: Proc. of the 30th SIGPLANSIGACT Symp. on Principles of Programming Languages20033849JensenOHMilnerRBigraphs and mobile processes (revised)2004MilnerRPure bigraphs: Structure and dynamics2006204160122PerroneGDeboisSHildebrandtTBigraphical refinement20112036MilnerRThe Space and Motion of Communicating Agents2009WuHGJinBHGanYWuGQBigraphical reactive systems based on nested sort2012399143151吴怀广金保华甘勇毋国庆基于嵌套赋类的Bigraph 反应系统模型2012399143151HoareCARCommunicating sequential processes1978218666677LeiferJJMilnerRTransition systems, link graphs and Petri nets20061669891047BundgaardMMilnerRUnfolding CSP. In: Proc. of the Reflections on the Work of C.A.R2010213228BirkedalLDeboisSElsborgEHildebrandtTNissHBigraphical models of context-aware systems. In: Proc. of the 9th Int'l Conf. on Foundations of Software Science and Computation Structure2006187201WuHGJiHLWuGQMiaoYCalculational bigraphical model of context-aware systems in ubiqutious computing environment2012391109114吴怀广姬厚灵毋国庆苗玥普适环境中上下文感知的带演算的Bigraphs 描述2012391109114AghaGActors: A Model of Concurrent Computation in Distributed Systems1986PereiraEKirschCSenguptaRdeSousa JBBigActors—A model for structure-aware computation2013199208Pereira1EPotiron1CKirschCMSenguptaRModeling and controlling the structure of heterogeneous mobile robotic systems: A bigactor approach2013KrivineJMilnerRTroinaAStochastic bigraphs20087396SevegnaniMCalderMBigraphs with sharing20155774373CalderMSevegnaniMModelling IEEE 802.11 CSMA/CA RTS/CTS with stochastic bigraphs with sharing2014263537561CalderMKoliousisASevegnaniMSventekJReal-Time verification of wireless home networks using bigraphs with sharing201480288310StellJDelMondo GThibaudRSpatio-Temporal evolution as bigraph dynamics2011148167WaltonLAWorboysMA qualitative bigraph model for indoor space2012226240ChangZMMaoXJQiZCApplying bigraph theory to self-adaptive software architecture200932197106常志明毛新军齐治昌Bigraph 理论在自适应软件体系结构上的应用200932197106ChenHLLiRFAnalyzing and verifying method for dynamic evolution software based on bigraphical theory2010121223052309陈洪龙李仁发基于Bigraph 理论的动态演化软件相关特性分析与验证方法2010121223052309ChangZMMaoXJQiZCAn approach based on bigraphical reactive systems to check architectural instance conforming to its style. In: Proc. of the 1st Joint IEEE/IFIP Symp20075766ChangZMMaoXJQiZCTowards a formal model for reconfigurable software architectures by bigraphs2008331334ChangZMMaoXJQiZCFormal analysis of architectural policies of self-adaptive software by bigraph2008118123LiuPPZhangYMoQShaoZResearch on software evolution process model based on bigraph theory201353014231426刘培培章勇莫启邵振一种基于Bigraph 理论的软件演化过程模型研究201353014231426WangLRongMZhangGQWangSResearch on bigraph based aspect oriented dynamic software architecture evolution2010379137140汪玲戎玫张广泉王昇基于Bigraph 的面向方面动态软件体系结构演化研究2010379137140YangXLiTAn AOP framework supporting dynamic evolution201238195255杨曦李彤一种支持动态演化的AOP 框架201238195255ZhangMShiLZhuLWangYFengLPuFA bigraphical model of WSBPEL. In: Proc. of the 2nd Joint IEEE/IFIP Symp. on Theoretical Aspects of Software Engineering2008117120BundgaardMGlenstrupAHildebrandtTHøjsgaardENissHFormalising higher-order mobile embedded business processes with binding bigraphs. In: Proc. of the 10th Int'l Conf. on Coordination Languages20088399WuHGWuGQWanLBigraphical model of service composition in ubiquitous computing environments2010658662ConfortiGMacedonioDSassoneVBigraphical logics for XML. In: Proc. of the 13th Italian Symp2005392399HildebrandtTNissHOlsenMFormalising business process execution with bigraphs and reactive XML. In: Proc. of the 8th Int'l Conf. on Coordination Models and Languages2006113129JinLFLiuLBigraphical semantics of seal calculus2008313522528金龙飞刘磊Seal 演算的偶图语义2008313522528ZhaiHWZhangWSCuiLCLiuHBAbrahamAA bigraph model for multi-route choice in urban rail transit. In: Proc. of the 2011 Int'l Conf. on Communication Systems and Network Technologies2011699703ZhaiHWZhangWSCuiLCShiJSLIHToward formal description to metro services mechanism based on bigraph models. In: Proc. of the 2011 Int'l Conf. of Soft Computing and Pattern Recognition (SoCPaR)2011285289ZhaiHWZhangWSCuiLCXieXZhangXGHigh-Confidence petroleum industrial critical systems research based on bigraphical models. In: Proc. of the 2011 Int'l Conf. of Soft Computing and Pattern Recognition (SoCPaR)2011290295LiCYManJFWangZBAn improved method for transaction footprints stripping with bigraph system20127921412148BirkedalLHildebrandtTBigraphical programming languages2004https://github.com/ale-f/big-redPerroneGDeboisSHildebrandtTTA model checker for bigraphs. In: Proc. of the 27th Annual ACM Symp. on Applied Computing (SAC 2012)201213201325PerroneGDeboisSHildebrandtTTA verification environment for bigraphs20139295104