基于嵌入的图重写和局部动作系统的理论与应用

网址：http://www.elsevier.nl/locate/entcs/volume51.html11页流程和本地操作Dirk Janssens1;2安特卫普大学数学与计算机科学系B-2610 Wilrijk，比利时摘要局部动作系统旨在作为一个统一的框架，用于一些类型的基于嵌入的图重写。本文第一部分提出了基于嵌入的图重写的真并发进程理论，并简要讨论了它在Petri网中的可能应用。第二部分讨论了地方行动系统的不同变体，并展示了它们如何在第一部分开发的框架中。1引言局部动作系统（LAS）[1]旨在作为基于嵌入的图重写系统的统一框架，例如NLC[2]，NCE[3]和许多其他系统。尽管大多数关于图变换系统的研究都是针对代数图重写[4，5]进行的，但基于嵌入的图重写具有许多有趣的特征：基于嵌入的系统的单个产生式对应于代数产生式的可能集合（每个可能的邻域对应一个），并且它们允许非常简单的并发概念。如果嵌入机制是合适的（如LAS的情况），则图的每对不重叠的子图可以同时重写，而不需要构造合并的产品。几种类型的Petri网，见，例如，[6]，可以用LAS建模。关于LAS的工作，例如，[1，7]，包括两个方面：本文分别介绍了具有嵌入的过程理论和局部作用系统。在基于嵌入的图重写中，产生式指定两个图l和r，以及嵌入要使用的关于l和r的附加信息1 由欧盟委员会德涅斯特河沿岸摩尔多瓦共和国网络GETGRATS提供部分支助2 电子邮件：dirk. ua.ac.bec2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2ni对于图gi=（Vi; gv;ge），i= 1;2，g1+g2是图的一个运算graph（V 1[V 2; g v+ g v; g e+ g e）. 对于关系CVV， C中的路径是机制 当使用这样的产生式将图g变换为图h时，则首先将g中的l的出现替换为r，然后使用嵌入机制构造h。因此，嵌入机制使用g（最初存在的结构）和r（创建的结构）以及作为生产的一部分给出的附加信息。2结构、图形和标签为了本文的目的，可以方便地使用下面的（nite，discrete）结构的概念。定义2.1一个结构是系统S=（V;（Ri）1in;（fj）1 jm），使得 V是一个集合，对于每个 i，1 i n，存在一个非负整数ni，使得Ri是 V上的一个 ni元关系，对于每个j，1j m，存在一个非负整数mj和一个集合Wj，使得fj是Vmj的一个 mj元部分函数 i n到Wj。V称为S的载波集。对 于 V的每个子集X，SjX表示由X诱导的S的子结构;因此SjX具有载体集X，关系Ri\ X和函数fjjXmj。图是由一组节点组成的结构，标签功能：一个用于节点标签，一个用于边缘标签。后者的域可以被看作是图的边的集合。在整个文件中，v和e表示节点和边标签的固定集合。定义2.2一个图是一个三元组g =（Vg; gv; ge），使得Vg是一个 集合，gv是从Vg到v的部分函数，ge是从Vg到e的部分函数。本文的一个基本思想是，产生式描述了可以组合以产生系统的过程的原始过程-系统是一组产生式。这种方法需要能够用不重叠的节点集合来组成图，因此假设节点和边标签v和e的集合是交换幺半群而不是集合。在这两种情况下，幺半群运算用+表示，中性元素用0表示。对于集合V，0V表示V上的图g，使得gv和ge是空函数。对于偏函数f 1：V 1！和f 2：V 2！其中 V1， V2是集合，（;+）是幺半群，f1+f2表示从V1[V2]到V1 [V2]的部分函数，使得对于每个x2 V1[V2]，（f1+ f2）（x）= f1（x），如果x2 Dom（f1）n Dom（f2），（f1+f2）（x）=f2（x），如果x2 Dom（f2）n Dom（f1），（f1+f2）（x）=f1（x）+f2（x），如果x2Dom（f1）\Dom（f2）. 标签上的幺半群运算可以推广我我1 2 1 2序列x 1;：; x n使得1n，对于1我n1，（xi; xi +1）2 C. C是非循环的，如果在C中不存在路径x 1;：; x n使得n > 1且x 1=x n。33嵌入过程在这一节中，提出了一些基于嵌入的图重写过程的形式化理论的想法。介绍了处理嵌入机制的一般方法，并在此一般水平上考虑了过程的各个方面：过程的顺序和并发组成，生产和系统的概念，以及过程的配置方式可能被定义。在本节的第一部分中，介绍了进程的概念，并演示了当假定进程可以顺序组合时，如何获得进程语义。在第二部分中，被认为是一种情况下，进程可以组成一个更一般的，并发的方式。3.1序贯复合过程一个过程是一个描述重写历史的结构，在“真并发”的意义上：因果关系被显式地表示。在这里提出的框架中，一个过程由四个部分组成：一组节点，代表重写历史中出现的所有节点;一个关系，代表这些节点之间的直接因果关系;一个图，代表重写历史过程中最初存在或创建的结构;以及一个结构，代表嵌入机制所使用的信息。不需要给出关于该级别的最后一个组件的进一步细节，因此，在该框架中，具体嵌入机制的定义包含两个部分：首先，用于过程的组件E的定义，其次，使用该组件E来构造由过程的执行产生的图的方式的定义。定义3.1一个过程是一个4元组p=（ Vp; Cp; Sp;Ep），使得 Vp是一个有限集合，CpVpVp是一个非循环关系，Sp是Vp上的一个图，Ep是Vp上的一个结构。由

下载后可阅读完整内容，剩余1页未读，立即下载