基于规则的嵌套图转换模型

《理论计算机科学电子札记》59卷第4期（2001年）URL：http://www.elsevier.nl/locate/entcs/volume 59. html15页s形嵌套图和图的变换Berthold Ho Mülmanna，1 Mark Minasb，2aTech nologiezentrumInforrmatik，UniverrsitéatBremen，Postfach 330 440，D-28334 Bremen，GermanybLehrstuhlfur？rP rogrammie rs prachen，Univer r sit？atE rl a ngen-Nu？n berg，Martensstr. 3，D-91058 Erlangen，Germany摘要本文描述了一个新的计算模型，基于规则的程序设计与图形和图表。使用现有的图嵌套概念，该模型定义了一种基于变量匹配的嵌套图转换的直观方式。引入形状规则来指定嵌套图的结构一致性条件形状规则为形状嵌套图变换的细化模型建立了一个可判定的类型规则。由于细化模型与图编辑器DIA GEN兼容，因此可以通过可定制的图接口进行扩展，以便指定基于规则的图转换。关键词：嵌套图，结构图类型化，嵌套图变换，图语言1介绍统一建模语言（UML[22]）表明，图语言在系统设计和编程中变得越来越重要本文是关于一种基于规则的语言的计算模型，用于图表编程。该模型使用图作为数据模型，因为实际上每种图都可以抽象地表示为图，即使图本身看起来不像图[1]。 为了达到在传统语言中，递归数据结构的表达能力，图已经通过嵌套的概念进行了扩展[5]。与用于软件建模的分层图的相关概念相反[3，7]，*这项工作得到了ESPRIT工作组图形转换应 用 （A PPLIGRAPH）的部分支持。1电子邮件地址：hof@tzi.de2电子邮件地址：minas@informatik.uni-erlangen.de由ElsevierScienceB提供200 1个按钮。 V. 操作访问和C CB Y-NC-ND许可证。米纳斯？霍夫曼2嵌套图是合成的，因为它们禁止跨越组件边界的边。图变换是图上基于规则的计算的丰富理论[21]。我们将图变换的简单概念，如边替换[4]和替代变换[19]，结合到一种基于变量匹配和实例化的嵌套图变换的新方法中。 我们发现这种直观，优雅，对编程特别有用，因为它类似于其他基于规则的计算模型，例如术语重写[15]。此外，我们引入形状规则，指定嵌套图的结构一致性条件。形状规则类似于函数语言中的代数数据类型定义，但更强大，因为子结构的共享也可以指定;它们也超越了基于图变换的其他编程语言的类型概念，如PRO GRES[24]，它只限制节点和边的标记和程度嵌套图变换被定义为形状嵌套图变换，通过使用形状作为一致的和可判定的类型规则，排除形状不佳的图。最后，我们证明了形状嵌套图变换与图编辑器生成器DIA GEN[16，12]是兼容的。这为计算模型提供了用户界面，该用户界面可以针对不同的用户定制。gram符号在特定的应用领域中使用，并将其转换为图转换的模型。本文的结构如下：第2节回顾嵌套图，图变换扩展到第3节。在第4节中，我们描述了图形状的具体化，并在第5节中对变换进行了细化，以使其遵循这种形状规则。概述了将形状嵌套图变换集成到DiaGen图编辑器生成器中 第6节最后，我们对相关和未来的工作（第7条）。致谢。我们感谢审稿人的宝贵意见，帮助我们改进了论文（希望如此）。2嵌套图我们对图的定义是为编程量身定制的。它在两个方面扩展了图的常见概念：• 边可以连接任意数量的节点，而不仅仅是两个节点，因此可以表示任何元数的关系。• 边可以包含图，其边可以再次包含图，使得图由嵌套的组件组成。出现在规则中的图具有可区分的节点，在这些节点处，它们可以被粘到其他图，并且还可以包含变量作为占位符。米纳斯？霍夫曼3X→ G→ X→∗∈∗∈C+CJ−y：=eJx：=e☛ ✟✡Δ✠☛✟☛✟✡✠✡✠+ C−PDD一x：=e可以用图形代替的地方。嵌套图形。设Λ是有限标签集和可数标签集，变量名。在Λ和X上的嵌套图的集合G（简称图）由元组G = AV，E，lab，att，cts A组成，元组具有节点的有限集合V和边的有限集合E，标签函数lab：EΛ，将节点序列分配给边3的附着函数att：E V，以及将边映射到嵌套图的内容函数cts：E。由于定义中的递归，嵌套图被定义为诱导图，在嵌套深度上是有效的：G=n0Gn，其中G0={}（其中是没有节点和边的空图），并且，对于任何深度n >0，G∈ Gn如果cts（e）∈ Gn−1对于每个边e∈E。如果s（e） =0，则边e被称为plain，并且rw也被称为e。IfehasK0附件和标签l ∈ Λ <$X，我们将其限定为k元，并作为一个l-edge。由变量名标记的边称为可变边（简称变量）。图G中的一个变量e是直的，如果它的连接是两两不同的。我们假设嵌套图中的所有变量都是普通的。一个图G称为平面图，如果它的所有边都是平面的，并且顶点通过清空G的框架的内容而获得的普通图G^isthe点图G，p是指具有可区别的点序列p V的图G=pV，E， ab， att，cts， p.如果p的长度为k，则称G为k元.我们常常只用图的分支来表示点图，而用pG来表示点图的点。例2.1[控制流程图]下面的图1显示了顺序命令式程序的三个控制Fig. 1. 三个控制流程图控制流程图中的节点表示执行状态;它们被画成小圆圈，如果是点，则填充。控制流程图中的最高点表示其开始状态，其余点表示停止状态。恒定的边表示ECHANISM步骤：分配和调用被绘制为框，并将一个前驱连接到一个后继状态;分支被绘制为菱形，并将一个前驱连接到一个真正的后继状态，3V1表示序列v1. v k在某个词汇表V上（v iV，对于1≤i≤k）。空序列由ε表示。米纳斯？霍夫曼4→⟨⟩→→一个虚假的继承国。分支和分支是普通的，分别用赋值语句和条件标记;调用是包含被调用子例程的控制流程图的框架。变量被绘制成椭圆形;它们将一个前趋状态连接到几个后继状态。箭头将前置状态链接到边，线条将其链接到后继状态;true并通过附加的子树resp来区分分支的伪G到这些线。图表的图片被包围在一个框中，该框可以在右上角包含其名称。图P和A是简单的和有点的，并且C包含单个调用帧。变量（在C中命名为Δ，在P中命名为D）是直的。形态学。图 之间的结构保持映射用于将一个图（的副本）识别为另一个图中的子图。设G=V，E， lab， att， ctsj，GJ=VJ，EJ， labJ， attJ， ctsJ是图.一态射m：G→GJ是一个三元组m=mV，mE，M<$，其中• mV：V→VJ和mE：E→EJ是保留标签和附件的节点和边映射：labJ（mE（e））=lab（e）anddattJ（mE（e））=m<$V（att（e））foralle∈E4• M=（m e：cts（e）ctsJ（m E（e）e∈E是边的内容之间的态射族.态射m是满射（内射），如果它的分支映射是满射（内射）。如果m是满射和内射，则称它是同构，并且图G和GJ称为同构，记为G=mGJ. （我们省略了索引xmifitisnotreelevant。）件. 框架以类似树的方式嵌套。其封闭框架的序列标识嵌套的图形组件。图G=V，E， lab， att， cts中边的出现数是边序列G={ε}|e∈E，w∈S（e）}然后，在某个出现点w∈G的分量G/w被给出为G/ε=G和G/（ew）= cts（e）/w一般假设。 对于本文的其余部分，我们假设图G的所有分量的节点和边是成对不相交的，并将V G，E G，lab G和att G定义为分量的（不相交）并[4]函数f：A B的扩张f<$：A<$B<$将空序列ε映射到自身上，而序列a1. a k到序列f（a1）上. f（a k）。米纳斯？霍夫曼5X各组分G/w的G.同样地，出现在G的所有分量的集合中的变量名用XG表示。边替换，上下文嵌入，变量实例化。图的边插入是定义上下文嵌入和变量实例化的基本操作，是图变换的辅助操作。将图分量G中的普通k元边e∈EG替换为带点的n元图<$U，p<$U记为G[e/U]，并分三步进行(i) 若G/w是e为顶边的分支，构造G/w与U的不交并，去掉e;(ii) 将attG（e）和p中的相应节点粘合起来，对于1. min（k，n）;5(iii) 将G/w替换为G中的此图。平边的替换是可交换的：无论是某些边在另一个边被另一个grap h U替换之前被一个graphU替换，还是被一个ward替换，都没有关系。一个图C是一个上下文，如果它在它的一个分支中只包含一个直孔变量，比如h。一个点图U到C的嵌入由C[h/U]给出。替换对x<$→U将变量名x与点图U相关联，其中所有点都是成对不同的。一个置换是一个有限集σ ={x1> → U1，. ，x k <$→U k}替换对，具有成对不同的变量名。图P的置换σ的实例化是通过将G中的所有xi-变量平行置换为图Ui的不同副本（1≤i≤n）而获得的，记为Pσ。由于边置换是可交换的，这唯一地定义了Pσ（直到同构）。例2.2[变量实例化和上下文嵌入]图2说明了图1中所示的图C、P和A上的操作。左图是通过代入σ={D <$→A}实例化P而得到的。 右图是Pσ在图C中的嵌入（这是一个上下文）。3图形变换通过将模式图嵌入到上下文中，在将其变量匹配到合适的子图之后，将替换图嵌入5因此，实际上只有min（k，n）个节点被识别。我们可以强制k=n，但这是一个类型问题，稍后再考虑。米纳斯？霍夫曼6]☛✟☛✟✡✠✡✠+ C−DD☛✟✡✠D<$c−+☛✟✡ ✠D→⇒∈⇒⇒⇒LuDPσx：=ex：=e+的C−C[h/Pσ]+−y：=eJCJx：=ex：=e+的C−z：=eJJ图二. 上下文嵌入和变量实例化图形转换。图变换规则t：PR（简称规则）由点模式图P和点替换图R组成，点模式图P中的所有点是两两不同的。一个规则t：P→R匹配图G ，如果存在一个上下文C和一个子图σsuchtC[h/Pσ]n=mG，对于一个简单的图是简单的. 三重数m，σ_n是G中的n个称之为环的指数，它将G变换为G_n=H_n=C[h/Rσ]，记为G_n=H.如果T是一组规则，我们写G如果有规则，T将G变换为H。这个关系是包含T的最小关系，并且在同构、替换和约束下是封闭的. 我们写了一封信，恢复xive-transitionsitivecloureofTsothatGTHexpressencettTtransformsn中的G到H0步。例3.1[控制流图转换]图3显示了控制流图的两个转换规则。规则l执行循环转换，规则u展开过程调用的主体。图4显示了使用这些规则的控制流程图的两个转换。规则l的模式图P、上下文图C和用于步骤H l J的替换σ如图1和图2所示。嵌套图变换是可判定的。定理3.2给定一个嵌套图G和规则t：P→R，可以计算基于该redex的变换G tH（如果它们存在）。☛✟→ →✡✠图三. 循环变换规则（左）和过程展开规则（右）米纳斯？霍夫曼7J+−y：=eJx：=eCJ<$c−+z：=eJJ⇒G/W¯W∈鲁勒丘见图4。 两个转化步骤我的律师。 对于G（w<$∈G）的一个比较对象G/ w <$，构造一个简化的计算过程，其中，对于任何发生w ∈ P，都有一个使图形比较对象P/w等于图形比较对象^的子块σw。这就是简单图匹配问题，它是可判定的[19，推论15]。变换GT H可以通过嵌入和实例化容易地构造。✷由于子环同构问题P=？ 对于任意的平面图P和G，只有S_G是NP-完全图，我们需要进一步的限制以使图变换是有效的。(This对其他所有类型的图都不限制模式大小的转换。）虽然对效率问题的深入讨论超出了本文的范围，但这是下面介绍的形状的一个动机。4形状形状分析已经被用于推断在命令程序中指针结构是否被形成为双向链表、根连接树等[23]。在这里，我们设计了一种方法来指定图形的形状，这种方式在命令式语言的级别上是不可能的（在指针完全隐藏的函数或逻辑语言中该规范基于边替换[4]，但我们立即采用了符合我们目的的术语。形状语法。标 签 l Λ 的柄图由一条直的k元l-边组成，该边连接到k个成对不同的点，并且由l·表示。(Thel·的k0元数是任意的，但对每个l都是固定的。设N是一个有限的形状名称集合。一个变换规则s：P→R是一个形状规则，如果它的模式P是一个形状名n∈N的柄图n·，并且它的替换R不包含变量。我们写P→R1|......这是什么？| R kfor shape rules with the samepattern. 形状规则执行边替换。H+−y：=eJCJx：=ex：=e+C−z：=eJJK+cJ−y：=eJx：=ez：=eJ<$c−+米纳斯？霍夫曼8DDD+E−D d+ E−DX：=E×一个形状规则的有限集合S导出一个形状系统<$G =<$G，N，S<$G。证明了S∈S={G∈G|n·n∈S G，n∈N}.已知形状系统的隶属度问题是可判定的[4，2.7节]：定理4.1存在一个判定某个图G是不是图形例4.2 [控制流图的绘制]图5显示了定义结构化控制流图形状的规则，这些控制流图（从左到右）是通过赋值、过程调用、顺序组合、条件语句、预检查和后检查循环构建的。由形状名称标记的边以灰色绘制。→|||||图五. 结构控制图我们选择了一种非常严格的图。[8]中的半结构化流图对于编译器中的数据流分析很有用，可以用类似的方式定义[4]。形状文法生成了一类图形语言，这似乎是可以称为上下文无关的最大类之一。(See[4，第2.5节]详细信息。）特别是，它们允许定义函数语言的递归代数数据类型，这些数据类型是用不相交的union +和笛卡尔积构造的。此外，双向链接或循环列表，叶或根连接树，以及其他采用结构共享的命令式数据结构也可以指定[9]。定理4.1表明，形状文法不能定义递归可排序的图语言。例如，不可能以这种方式定义任意的控制流图然而，如果除了这里使用的形状规则之外，还允许一种非常简单的嵌入规则，那么也可以定义任意的控制流图，并且仍然可以确定成员资格[16]。5Shapely图变换我们现在定义形状图，并细化图变换，以便保持形状。本节中的结果的直接证明如下：DDE−+∈ G米纳斯？霍夫曼9→∈ G<$[<$∈在[11]中。形图。 在本文的其余部分，我们固定一个形状系统，<$G，N，S<$，并且要求形状名N在嵌套图G∈ G中不作为标签出现。此外，我们假设每个变量名x∈ X都有一个形状名type（x）∈N。我们定义了一个（点）图G的形状[G]，通过用它的形状名类型（x）重新标记每个x-变量，对每个x∈ XG。AgraphGisn-shap edifn·公司简介为我们的孩子N. 然后我们写type（G）=n。然后，成形图的集合由G={G∈G|n·n∈S [G∈ N， n∈N}.如果S是type（x）-shaped的，则置换对x<$→S，p<$是shaped的成形置换σ由成形置换对组成。形状转换。从现在开始，我们将注意力限制在通过shapely规则、使用shaped上下文和替换来转换shaped图上。规则t：PR是shapely的，如果它的模式图和替换图P和R是shaped的，使得type（P）= type（R）。 如果存在一个赋形上下文图C∈ G<$，其类型（Δ）=类型（P），且在此基础上，提出了一个满足C[h/P σ]n= G的子结构σ. 把G转换成gra p hHσ= C[h/Rσ]，记作G$tH。例5.1[Shapely控制流图变换]本文中的所有控制流图都是结构化的，即根据d.因此，图3中的规则是有形状的，图4中的转换也是有形状的。形状规律是一致的，因为形状变换的结果是再次成形的。如果规则的替换图不包含未出现在其模式图中的变量，则shapely变换保持图无变量。(this是重要的，因为在大多数情况下，只有无变量的图应被转换。定理5.2（1）若G$tH按某种形状规则t：P→R，则G∈ G<$设H∈ G，且type（H）= type（G）。(2)如果XR<$XP且G是无变量的，则H也是无变量的。定理4.1使有形图变换可判定：由于某个图是否有形是可判定的，因此也可判定置换是否有形，以及规则是否有形。一旦我们检查了规则，以及shapely变换的开始图G，检查redex的上下文和替换是否成形不会引起任何开销;相反，它使确定它们变得更容易米纳斯？霍夫曼106将图表可视化为图表图形和图形变换应用作计算模型DIA PLAN语言用图表编程。DIA PLANpro-gram在（嵌套）图上执行计算，基于（shapely）图内部转换，但应使用图表表示的图形与程序的用户进行通信图的一个实现，然后再回来：迪亚普兰因此，必须将图表转换为• 当用户创建图表作为程序的输入时，必须将其转换为图形表示，以便在内部进行处理• 如果要向用户显示某些计算的结果，则必须将内部表示该结果的图形转换回图表。DIA GEN工具[16]允许从基于图变换的图语言的形式规范生成图编辑器。它已经支持这些任务：使用生成的图编辑器编辑的图在内部由第4节中描述的形状图表示。形状系统是规范的主要组成部分，DIA GEN根据该规范生成图表编辑器。下面我们将解释DIA GEN如何实现图形和图表之间的转换。6.1将图表转换为图形当通过在屏幕上排列图表组件来自由编辑图表时，必须将其转换为内部表示，即，DIA GEN中的图形。该转换分两步执行：首先，将图转换为布局图，其中边表示图组件，节点表示组件的连接区域附件区域是一个图组件可以连接到其他图组件的特殊部分。组件（例如，线的端点）。附加的空间关系边用于表示附接区域之间的这种连接。在第二步骤中，然后通过将图组件组并行转换为图符号，将该图转换为超图模型。虽然布局图与图的可视化表示密切相关，但超图模型从可视化细节中抽象出来。超图模型然后经受由图解析器执行的语法分析。由于图已经被转换成图，所以图中的语法错误可以由图解析器检测到生成的编辑器显然提供了将图转换为图的方法，以便根据这些图进行计算。但是DIA GEN也给出了一个检查图形形状的解决方案。生成的图编辑器通过基于上下文无关图的图解析器进行语法分析有嵌入规则的文法[1，16]。这些扩展是必需的，因为上下文无关语法本身不足以描述语法米纳斯？霍夫曼11任意的图表语言。这些扩展也可用于扩展形状系统的表现力，并且同时具有能够根据这样的扩展形状系统检查图形形状的解析器。6.2将图表转换为图表到目前为止，DIA GEN的编辑主要是将图表转换为图形。 但是系统还提供了一些基本的支持，用于从图形创建图表DIA GEN允许指定当解析器已经创建了表示图的语法结构时，如何从其构建块创建图。该机制简单地基于附加到文法产生式的属性评估规则。例6.1[图编辑器]作为运行示例使用的结构化控制流程图有两种非常不同的图表示：控制流程图和Nassi-Shneiderman图。图6显示了控制流程图编辑器（左）和Nassi-Shneiderman图编辑器（右）的快照。快照显示图4中所示的图形H。见图6。 图4中图H这两个编辑器都是由DIA GEN生成的。两者都使用控制流图作为它们的抽象语法表示。注意，编辑器显示框架的内容（包含过程体的图在不同的窗口。执行DIA PLAN程序的场景如下：• 图编辑器提供用户界面，用于创建程序的输入，并显示其执行的结果。米纳斯？霍夫曼12• 从该界面调用程序的操作，例如通过菜单项。这将触发操作的执行，包括从图到图的必要转换，以及从图到图的转换。7结论我们用嵌套的合成概念扩展了图。这些图不再被称为层次图（如[5，11]），因为这个术语主要用于具有非合成的结构交叉边的结构图我们已经设计了一个嵌套图变换的概念，它以一种简单的方式将项[13]（函数符号上的树）的重写扩展到图上的树（即嵌套图）：变换替换规则模式中的变量，将实例化的模式嵌入到上下文中，然后将实例化的替换插入到该上下文中。从编程的角度来看，这种图形转换的方式似乎非常直观。此外，它可以很容易地通过一致和可判定的形状规则来细化，并且还可以允许更有效的实现。最后，这种转换方式可以与图工具顺利集成。我们希望这可以作为提出另一种图变换的借口。相关工作。 T.W. Pratt可能是第一个定义嵌套图语言的人[20]。他通过上下文无关的图文法来规范编程语言的语义Engels和Heckel [7]研究了层次图变换作为系统建模语言（如UML[22]）的基础。它们允许组件之间的边（穿过框架边界），这在该应用领域，但不足以编程，因为它会放弃嵌套图的组合性。替代图变换是层次图变换的（适度）扩展[5]，其中变量表示帧的全部内容在我们的变换中，变量可以表示任意子图是至关重要的。Busatto等人 [3]研究了层次图变换的一般概念，通过该概念可以模拟其他方法[2]，也可以模拟[5]，并且可能也可以模拟shapely图变换。我 们 定 义 形 状 的 方 式 受 到 了 P. Fradet 和 D.LeM′etayeronS tr ucturedGamma[9]没有使用sss结构多集重写，这是一个可以直接“翻译”为图变换和边替换的概念。未来的工作。变换可能是高度不确定的。这可能会导致回溯的过载。因此，非确定性必须限制到编程真正需要的程度。良好的规则模式、嵌套结构和形状设计已经可以减少不确定性。米纳斯？霍夫曼13然而，即使对于给定的上下文和规则，也可能存在将规则匹配到主机图的许多替换σ。因此，一个重要的目标将是限制替代所允许的非决定论。例如，可以要求模式中的每个帧最多包含一个变量。这将使规则匹配几乎与[5]中一样具有确定性嵌套图由有限的组件树组成在某些应用中，可以共享具有相同内容的组件，例如，相同过程的控制流程图。关于折叠表示的充分性的讨论可以从关于项的折叠表示的结果中得出[18]。甚至组件的循环共享也是有意义的，例如。用于表示具有递归调用的控制流程图然后可以使用关于无限项的循环表示的结果[14]。图只是根据它们的（图形）表示对值进行分类的一种更多的类型规则将是有用的，例如在PROGRES[24]中。此外，上下文无关的图形语言可能过于局限于指定在某些应用程序中出现的图形的形状。然后可以考虑Church-Rosser图语言[17]前景。 Shapely图形变换将成为计算机图形处理的一种新方法。基于规则的编程语言DIAPLAN的抽象模型图[10]。 其他概念产品型号：迪亚普兰在此基础上，• 带参数的转换谓词应允许从转换序列中抽象• 应用条件和谓词参数应允许以命令或功能方式指定控制• 类应封装形状规则和转换谓词。• 像数字和字符串这样的原始值应该作为第一类对象集成到图模型中。这将使DIA PLAN成为一种成熟的基于嵌套图的可视化编程语言。与前面部分讨论的DIAGEN可以根据特定的应用领域定制任意的图表符号。引用[1] R. Bardohl，M. Minas，A. Sch？r，和G。 天泽河一种将图形转换为视觉语言的方法。在Engels et al.[6]，第3章，第105[2] G. Busatto和B.霍曼。比较分层图变换的概念。电子笔记理论计算机科学，2001年。出现。米纳斯？霍夫曼14[3] G. Busatto ， H. Kreowski 和 S. 库 斯 克 一 个 抽 象 层 次 图 数 据 库 。Technicacalrepor t ， FachbereichMath e m atik-Inform atik ， UniverrsitaütBremen，to appear 2001.[4] F. Drewes ， A. Habel 和 H.- J. Kreowski. 超 边 替 换 图 文 法 。 在 Rozenberg[21]，第2章，第95[5] F.德鲁韦斯湾Ho Muslimann，和D.丰满。层次图变换。计算机与系统科学杂志，2001年出版。（一个简短的版本出现在计算机科学讲义第1784期，第98-113页，2000年）。[6] G. Engels，H. Ehrig，H.- J. Kreowski和G.罗森伯格，编辑。图文法与图变换计算手册，第二卷：规范与程序设计。世界科学，新加坡，1999年。[7] G. Engels和R.海克尔 图转换作为系统建模和演化的概念和形式框架。在usMontanari，J.罗林，以及E. Welz，编辑，自动机，语言和编程（ICALP 2000 Proc.），第1853号，计算机科学讲义，第127斯普林格，2000年。[8] R. Farrow，K. Kennedy和L.祖科尼图文法与全局程序数据流分析。在Proc.17th Annual IEEE Symposium on Foundations of Computer Science，第42-56页[9] P. Fr ad etandD. 我也是。STRUCTURDGamma.计算机程序设计科学，31（2/3）：263 -289，1998.[10] B.霍曼。从图形转换到基于规则的程序设计。 在M。 Nagl，A. Schurr和M.Mu ？ n ch ， editors ， Int'lW or k s hop on Applications of GraphTransformations with Industrial Relevance（Agtive '99），Selected Papers，number 1779 in Lecture Notes in Computer Science，pages 165-180.斯普林格，2000年。[11] B.霍曼。Shapely分层图变换。 视觉语言与形式化方法国际IEEE ComputerPress，2001.[12] B. Ho Mushmann和M.米纳斯图语法和语义的通用模型在J.D. P. Polim等人，编辑，ICALP Workshops 2000，No. 8 in Proceedings in Informatics，pages443卡尔顿科学。[13] G. 休 特 Concluent reductions ： Abstract properties and applications to termrewriting systems. Journal of the ACM，27（4）：797[14] R. Kennaway，J. W. 克洛普河睡觉，F。J. 德·弗里斯正交项重写系统中的transfinite约简信息与计算，119（1）：18米纳斯？霍夫曼15[15] J. W. 克洛普术语重写系统。In S.Abramsky，D.M. Gabbay和T. Maibaum，编辑，Handbook of Logic in Computer Science，第2卷，第1-116页。牛津大学出版社，1992年。[16] M.米纳斯基于超图变换的图表编辑器生成器的概念与实现。《计算机程序设计科学》，2001年出版。[17] D.丰满。Church-Rosser超图语言1999年9月在德国绍恩堡-埃尔姆斯哈根“自动化和形式语言”讲习班上的演讲[18] D. 丰满。项图重写。在Engels et al.[6]，第1章，第3[19] D. Plump和A.哈贝尔图形统一和匹配。 在j. E. 库尼，H. Ehrig，G. Engels和G.图文法及其在计算机科学中的应用，计算机科学讲义第1073期，第75-89页。Springer，1996年。[20] T. W.普拉特使用层次图语法定义编程语言语义。In V. Claus，H. Ehrig和G.图语法及其在计算机科学和生物学中的应用，计算机科学讲义第73期，第389-400页。斯普林格，1979年。[21] G.罗森伯格编辑图文法与图变换计算手册，第一卷：基础。世界科学，新加坡，1997年。[22] 朗博岛Jacobson和G. Booch. 统一建模语言参考手册。对象技术系列。艾迪森·韦斯利1999年[23] M.萨吉夫，T. Reps和R.威廉用破坏性更新的语言解决形状分析问题。ACMTransactions on Programming Languages and Systems，20（1）：1[24] A. Sch ürr，A. 是的，还有A。 Zundorf. 该产品是一个理想的环境：L语言和环境。在Rozenberg [21]，第13章，第487