没有合适的资源?快使用搜索试试~ 我知道了~
网址:http://www.elsevier.nl/locate/entcs/volume51.html10页节点重写1的上下文无关超图文法Renate Klempien-Hinrichs2Universit地址:Bremen,FachbereichMathematikInformatikPostfach 33 04 40,28334Bremen,Germany摘要将上下文无关的图文法方法-并发节点重写推广到超图,产生了已知的最强大的上下文无关超图语言设计技术。本文总结了作者的博士论文的一部分,证实了这一说法的生成能力的所谓的C-hNCE语法的报告。1引言在文献中,两个主要的替代品被认为是广义的上下文无关的语法从字符串到图形的概念。hypergraphs,参见[5]:conuent node-rewriting graphgrammars(参见[6])和hyperedge- rewriting hypergraphs(参见[4])。每种方法都有其独特的优点:在节点重写文法中,可以获得大量的边,而在超边重写文法中,超边可以单独处理。引发本文所述工作的设想是制定一个框架,将两种方法的长处结合起来。与节点重写相反,超边重写在超图语法中很早就被研究过。 由于超图只不过是图的一般化,其中超边与边不同,因为它可以具有任意长的连接节点序列(即, 不一定是两个),将组合框架发展为超图文法是合理的。然而,在超图中缺少节点重写的概念。因此,第一步是推广节点重写1 本研究得到了EC TMR网络GETGRATS(图形转换系统的一般理论)和ESPRIT基础研究工作组APPLIGRAPH(图形转换的应用)的部分支持。2 电子邮件地址:rena@informatik.uni-bremen.dec 2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2H从图到超图[8]。很快,上下文无关节点重写超图文法本身就很有趣。因此,在本文中,总结了作者的博士论文[11]的一部分,研究了所谓的C-hNCE文法在第2节中给出一些初步概念之后,第3节介绍了C-hNCE文法。在第4节中,这种方法的生成能力被证明包括其他主要的上下文无关超图语法方法,即那些基于超边重写的方法。关于单独的句柄重写。第五节研究了C-hNCE文法中超边的最大秩对生成超图语言的影响。最后,结论涉及一些进一步的方面。关于详细的证明,读者可以参考[11]。2预赛在本文中,设N=f0;1;2; :g为非线性整数的集合,N+=Nrf0 g,且[n]=f1; :;n g对n2N. 上的(简单、有向、节点和超边标号的)超图是元组H =(VH ; EH实验室H)其中VH是一节点的集合,EHV是一组超级边缘,还有实验室H:V H!是用labH(v)标记节点v的映射。给定一个超边e =(;v1 vn)2 EH,我们也写labH(e)=为它的标号,attH(e; i)= vi为它的第i个连接节点,rankH(e)= n为它的秩;此外,每个i 2[n]都称为e的一个tensor在图画中,超图的节点用圆表示,超边用正方形表示,并且触角由编号的线表示,例如12。标签写在节点的旁边。它所指定的超边两个超图G和H是同构的,如果存在一个双射f:VG!使得EH =f(; f(v1)f(vn))j(;v1vn)2 EG g,对于所有v 2 VG,实验室H(f(v))=实验室G(v)。同构于(具体)超图H的所有超图的集合用[H]表示(也称为抽象超图)。上的所有(具体)超图的集合记为H,所有抽象超图的集合记为[H]。超图语言是[H]的一个子集,所有 超 图 语 言 的 集 合 用 LH 表 示 , 语 言 的 秩 L 2 LH 是 rank ( L ) =maxfrankH(e)j[H] 2 L; e 2 EH g。3超图中的上下文无关节点重写当用超图代替一个结点时,与该结点关联的超边必须转化为与被替换超图的结点关联的超边。为了指定这种超边的变换,超图被连接关系扩充。我们解释这是如何工作后,- mally界定这些关系。具有嵌入的超图是一对(H; C),其中H是环上的超图,C(([fg))((N+[VH)),32113122XHj jRHJJ=0X )Fig. 1.超图关系中结点的代换,是H上的一组连接指令。设H是一个正图,v2v,(H0;C) 是一个边为d且H与H0不相交的正图.然后用y(H0;C)代替v,得到hy边图H[v=(H0;C)],如下:将v和它的两个hy边的交点一起去掉,得到余数H 的H;添加H0 到H;并连接H0和H 根据连接关系C:当verC包含连接指令(ex=cr),并且H包含与v相关的超边e,该超边e表示存在部分ex时,根据创建部分CR创建。 超边e匹配ex =(;x 1如果是e的标号,m是它的秩,并且对于所有i2[m],x i=如果att H(e; i)= v且x i=lab H(att H(e; i)),否则。则cr =(;y1yn)创建超边e0 对于所有j2[n],att(e0;j)=y,如果y2V且att(e0;j)=att(e;y)如果y2[m]。 我们不允许其创建部分产生不必要的影响(即, 其中yj2=[m])或对未知数的影响(即, 其中yj2[m]和xyj=)。例3.1考虑带嵌入u1(H; C)=B;8(ex3= ; 1 2u1);(ex3= ; 1 2u2);91C2u2X :(ex2=;1u1u2);(ex2=;1u2);A其中ex3 =(;)且ex2=(;),即,exk识别超边最后一个tennis到被替换的节点。图1显示了用(H; C)替换左超图中的X标记节点v: v连同它的关联超边一起从超图中移除,H插入到它的位置,上面的超边既不匹配ex2(因为它的秩为3)也不匹配ex3(因为第二个,而不是最后一个tenant抓住v),因此保持删除,下面的超边匹配ex2,因此产生两个嵌入超边。邻域控制嵌入的结点重写超图文法(简称hNCE文法)是一个元组NG=(N; T的; P; S),其中N和T分别是非终结符和终结符的不交集,P是形式X::=(R; C)的乘积的不交集,其左侧为X2 N,右侧为N[ T]上的嵌入为(R; C)的超图,S2 N是NG的初始非终结符.由一个S-标号结点和无超边组成的超图S是NG的公理或初始超图。NG的秩,记为rank(NG),是最小的k2N3122v11@4HH[v;p]PPPu0S::=p11X;;CCX::=(H; C)p2X::=(p3;f(ex3=;1 2u)g)图二.属于例3.2的语法的产生式,具有例3.1中的(H; C)和ex3,并且唯一的终结符未被表示使得对于产生式的所有右侧(H;C),e 2 EH和(ex=cr)2 C,秩H(e);秩(ex);秩(cr)设 H 和 H0N[T , v2V] 上 的 behypraphs其中 lab ( v ) =X , p =(X::=(R; C))(的同构拷贝),R与H不相交。 则p可以应用于H中的v,产生超图H0 =H[v=(R;C)],其中h表示为H)H0或H)H0. 一个推导H)的 H0由许多传票生产应用程序组成。集合S(NG)=fH2HN[T(jS)Hg含有汞的形态L(NG)=f[H]2[HT]jH2S(NG)g是生成的hy超图语言如果两个文法生成相同的语言,那么它们是等价的例3.2对于k 2,有序k-锦标赛是一个超图,其中节点可以按无重复序列w排列,使得超边都是秩为k的超边,其连接序列是w的子序列。可以生成所有有序k-竞赛图n的k-竞赛图集S )X )X )p1 p2 p3图三.一个产生有四个节点的有序3-竞赛图的推导(触角从左到右排序)通过HNCE语法。对于k = 3,这样的文法是NG =(N; T; P; S),其中N = fS; Xg,T =fg,并且P包含图2中所示的三个产生式。图3中描绘了NG中的推导,其产生具有四个节点的有序3-锦标赛。一个文法在[2]的意义上说是上下文无关的,如果它是结合的和连续的。(This这意味着,在使用导出树的规范概念的情况下,给定导出树的不同遍历总是产生相同的超图。hNCE替换到具有嵌入的超图的直接扩展是关联的,即,我们有(H; C)[v1 =(R1; C1)[v2 =(R2; C2)]] =(H; C)[v1 =(R1; C1)][v2 =(R2;C2)]1 231122BB@A5对于嵌入为(H; C);(R1;C1);(R2;C2)且结点为v12的6M0 0VH;v 22VR1. 然而,对于conuence来说,情况并非如此。因此,我们是:一个hNCE文法NG=(N; T; P; S)是conuent(简称C-hNCE文法),如果对所有的乘积形式H,P中所有的乘积X1::=(R1;C1),X2::=(R2;C2)的(同构拷贝)使得H;R1;R2互不相交,且所有的v1; v2 2VH,其中labH(v1)=X1,labH(v2)=X2,我们有H[v1 =(R1; C1)][v2 =(R2; C2)] = H[v2 =(R2; C2)][v1 =(R1; C1)]:现在让我们转向一类hNCE文法,其中在重写节点期间创建的所有嵌入hyperedges必须与替换超图中的至少一个节点关联。这意味着,一个秩大于0的超边,出现在一个连续的形式是尽快产生其入射节点。形式上,设(R; C)是一个具有嵌入的超图。一个连接指令(ex= ;y1yn)是远程的,如果没有i 2 [n],yi 2 VR.如果hNCE文法的产生式的右侧不包含远程连接指令,则该hNCE文法是无远程的(简称hNCErf4超图生成能力两种主要的上下文无关超图重写方法是超边重写(参见[4])和分离句柄重写[3]。两者都可以通过当前hNCE重写来模拟[9]。超边重写(HyperedgeRewriting,HR)是最早的上下文无关超图重写技术。在这种方法中,一个非终结的超边指定了它的附着节点序列,它将与替换超图的所谓外部)见图4。 超边缘重写上具有外部结点的超图是对(M;ext),其中M是上重3超图和ext 2 V是一个两两相异的外部节点图4中的示意图说明了如何将具有外部节点(M0;ex t)的超图替换为超图M中的一个边缘e:移除e(不包括其连接节点),产生M的余数M;将M添加到M ;以及通过融合M 0的第i个外部节点来连接M和M(由灰色的y和i表示)与e的第i个atta ch enode。3 在多重超图中,可能有多个超边具有相同的标号和连接序列。13212371KIj我们定义了一种类似于hNCE语言的HR文法及其生成语言,并说如果生成语言中的超图是简单的,则HR文法是超图生成HR语法自然是上下文无关的。HR重写可以通过hNCE重写来模拟,其思想如下:向每个非终结超边添加一个节点,该节点将被重写而不是超边。然后移除HR产生式右侧的外部节点,并将其附带超边生成为嵌入超边。此外,还需要以下事实:(1)HR文法可以约简,使得它们只包含有用的非终结符。 (2)在一个简化的生成超图的HR文法中,没有一个顶点形式包含两个平行的终端超边。(3)对于每一个超图生成HR文法,可以构造一个等价的无外部边HR文法(外部边是只与外部节点关联的终端边定理4.1(HR重写的模拟)对于 每个超图生成HR文法,可以构造等价的C-hNCE rf文法。分离句柄重写,简称S-HH,是从超边重写发展而来这个想法是更换手柄,即,超边E及其关联节点,具有具有所谓端口节点的超图,其中端口节点是携带一个或多个自然数的节点。然后,对于每个i端口v,创建入射到e的第i个附接节点的每个超边的副本,并使其入射到v而不是i端口。)图五. 句柄重写上有端口的超图是一对(H;port),其中H是上无秩为0的超边的无节点标号超图,port是N+VH的一个子集.对于(i; v)2端口,v被称为i端口,i是v的端口号。图5中的sk etch示出了如何将具有端口(H0;p或t)的超图替换为超图H中的超边e的句柄将e连同其附接节点及其所有关联超边一起移除,产生H的余数H;将H0添加到H;并根据关系端口(i端口由灰色的i指示连接H0和H,通过在t(e;i)处为H中的每个hyp边e0创建(其中,h与att(并且对于每一个CH组合,; :;viknodes在H0中,v一个ij-port,一个副本其中,每个Chtenthh(forj 2[k])。12311,228我们定义了类似于hNCE语言的HH文法及其生成语言一个HH文法是分离的(简称S-HH文法),如果在其产生式的右边,两个不同的非终结超边从来没有一个共同的关联节点。S-HH文法自然是上下文无关的。S-HH重写可以通过hNCE重写来模拟,其思想如下(参见[3,引理4.1],其中处理了图生成S-HH语法的情况):将每个非终结符句柄收缩到一个节点中,该节点将被重写,而不是超边。然后,通过hNCE重写的嵌入机制执行与非终结符句柄关联的超边的乘法定理4.2(S-HH重写的模拟)对于每个S-HH文法,可以构造等价的C-hNCE rf文法。文[3]证明了由HR重写生成的简单超图的语言类分别是:由S-HH重写是无与伦比的:分离的例子是完全图(没有HR语言)和变体所谓的点树(没有S-HH语言)。这些语言的联合是C-hNCErf语言,它不能由HR语法或S-HH语法生成。定理4.3(适当包含)C-hNCE rf语言类适当包含HR语言类和S-HH语言类的并集。5C-hNCErf的秩和阶一致 语言对于HR文法,增加文法中出现的超边的最大秩会导致生成能力的适当增加[7,第五章,定理2.7]。相比之下,只要一个秩为k的超图语言可以用一个无远程的C-hNCE文法生成,那么一个等价的文法就可以被构造出来,其中只出现秩高达k的超边[10]。这一结果表明,每一个远程免费的C-hNCE图语言可以生成一个并发的节点重写图语法。定理5.1(秩定理)设k 2 N.对于生成秩为k的语言的每个C-hNCE rf语法,可以构造秩为k的等价C-hNCE rf语法。素描证明。下面,我们证明了每个C-hNCErf文法都有一个标准形式,其中超边的秩在嵌入过程中不会降低。生成秩为k的语言的这种C-hNCE语法仍然可以依赖于秩大于k的非终结标记的超边来从所生成的语言中排除仅具有终结节点的抽象形式,但是第二范式定理指出可以移除这些所谓的阻塞超边。从这些正规形式结构中产生的文法可以被变换为秩为k的文法。ut90000如果连接指令不是远程的,则该连接指令是链接保持的,它识别到被替换节点的超边恰好具有一个tenches,并且它创建一个超边,对于所识别的超边的每个tenches,该超边具有一个tenches附加到同一节点。如果hNCE语法中的所有连接指令都是链接保留的,则该语法是链接保留的。定理5.2(链路保持范式)对于每个C-hNCE rf文法,可以构造等价的链路保持C-hNCE rf文法。如果没有其节点是终结符的实体形式包含非终结符(即,阻塞)超边缘。定理5.3(非阻塞范式(参见[6,定理1.3.21]))对于每个C-hNCE文法NG,可以构造等价的非阻塞C-hNCE文法NG。如果NG是无远程或链路保留的,那么NG也是如此。定理5.1特别指出,图的每个C-hNCErf语言可以由其中指定秩至多为2的超边的文法生成。这可以用于表明,由C-hNCErf文法生成的每个图语言也可以由并发节点重写文法(所谓的C-edNCE文法)生成。然而,图形生成C-hNCErf语法可以包含秩小于2的超边的规范,其中只有那些与一个非终结节点(所谓的悬垂节点)关联的超边不能总是在不改变语言的情况下被移除一个hNCE文法是无悬垂的,如果在其产品的超图或连接指令中没有指定悬垂。定理5.4(无悬挂范式)对于每一个保持链接的hNCE文法NG,可以构造一个等价的保持链接的hNCE文法NG,它是无悬挂的。如果NG是并发的或非阻塞的,那么NG也是如此。定理5.5(C-edNCE范式)对于每个图生成C-hNCE rf文法NG,可以构造等价的C-edNCE文法。6结论C-hNCE语法目前代表了最强大的已知上下文无关超图重写方法,适当地推广了超边和分离句柄重写[9]。然而,无远程C-hNCE语法的图形生成能力与C-edNCE语法的图形生成能力一致[10]。图6的图表总结了这些关系,其中L(X)表示由X-文法生成的语言类,LH表示简单超图语言,LG表示图语言。由于节点重写文法在[2]的意义上是上下文无关的,当且仅当它们是连续的,因此很自然地会问,对于任意的10L(C-hNCErf)L(S-HH)L(HR)\LHL(C-edNCE)=L(C-hNCErf)\LG见图6。 发电能力hNCE语法,是否一致。答案是肯定的[8],尽管这个问题很难处理:[11]中详细描述的算法在时间上以输入语法大小的双指数形式运行。因此,应该像[6]那样研究静态连续性的概念。超图中的并发节点重写的优越生成能力似乎使引言中讨论的激励思想,即将节点和超边重写的优点结合到一个框架中,过时了。然而,情况并非如此,如以下示例所示。已知的是,并发节点重写允许生成语言,例如(a)所有完全图,(b)具有由特殊边标签区分的生成树的所有完全图,或(c)所有有序2-竞赛图的集合。现在考虑以下带有外部节点的图的语言:2 ;12 g:将此语言替换为上面的节点替换语言,即,为图中的每条边选择无论是删除还是保留它,分别产生(a)所有图,(b)所有连通图和(c)所有非循环图的集合。可以直观地清楚的是,这些语言可以由关联和并发类型的语法生成,其中节点重写和超边重写都可以发生,例如[12]的基本原子替换(BAR)语法。然而,它们不能由任何已知的上下文无关(超)图语法类型生成。事实上,BAR文法不是[2]意义上的文法,因为相同产生式的不同应用不一定产生相同数量的非终结项。然而,它们值得进一步研究,因为它们允许以直观的方式指定有趣的图和超图语言。BAR文法基于节点重写步骤和超边重写步骤的直接结合,产生式的定义和它们的应用借用了两种原始的且非常不同的文法方法。应该注意的是,拉回重写(参见[1]和其中的参考文献)提供了一种形式体系,其中超图中的超边重写以及节点重写可以以统一的方式指定因此,这种方法可能特别适合于继续研究超图文法与节点和超边重写。11引用[1] Michel Bauderon,H el ene Jacquet,and Renate Klempien Hinrichs.拉回重写及其应用。这一卷。[2] 布鲁诺·库塞尔。上下文无关重写的公理化定义及其在NLC图文法中的应用。理论计算机科学,55:141{ 181,1987。[3] Bruno Courcelle、Joost Engelfriet和Grzegorz Rozenberg。处理重写超图文法。计算机与系统科学杂志,46:218{270,1993。[4] 弗兰克·德鲁韦斯,安妮格雷特·哈贝尔,汉斯·约格·克鲁斯基。超边替换图 文 法 。 In G. Rozenberg , 编 辑 , Handbook of Graph Grammars andComputing by Graph Transformation。 第一卷:基础,第2章,第95页{162。World Scienti c,1997.[5] Joost 恩格尔弗里特上下文无关图文法。在 G. 罗森伯格和A. Salomaa,编辑,形式语言手册。第三卷:超越语言,第三章,第125页{213。Springer,1997年。[6] Joost Engelfriet 和 Grzegorz Rozenberg 。 节 点 替 换 图 文 法 。 In G.Rozenberg,编辑,Handbook of Graph Grammars and Computing by GraphTransformation。第一卷:基础,第1章,第1页{94。World Scienti c,1997.[7] 安纳格雷特·哈贝尔。Hyperedge Replacement:Grammars and Languages,卷643计算机科学。Springer,1992年。[8] 雷娜特·克伦平-韩瑞克斯超图中的节点替换:超边替换的模拟和连通性的判定。在J. Cuny,H. 埃里希G. Engels和G. Rozenberg,编辑,Proc. Fifth Intl.图形语法及其在计算机科学中的应用研讨会,计算机科学讲义第1073卷,第397页。Springer,1996年。[9] 雷娜特·克伦平-韩瑞克斯超图中 上下文无关节点重写的生成 能力。Grammars,2:211{221,1999.[10] 雷娜特·克伦平-韩瑞克斯上下文无关节点重写超图文法的范式。计算机科学中的数学结构出现。[11] 雷娜特·克伦平-韩瑞克斯上 下 文 无关超图文法。节点和超边重写及其在Petri网中的应用。博士论文,大学2001年在不来梅[12] 雷娜特·克伦平-韩瑞克斯基本原子替换语言中的超边替换。已提交出版。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功