网址：http://www.elsevier.nl/locate/entcs/volume51.html13页结构化建模与GRACE？汉斯-JorgKreowski，GiorgioBusatto，Renate Klempien-Hinrichs，Peter Knirsch，SabineKuske不来梅大学计算机科学P.O. Box 330 440，D-28334 Bremen，Germanyfkreo，giorgio，rena，knirsch，kuskeinformatik.uni-bremen.de摘要在本文中，我们勾勒和说明的图形和规则为中心的建模语言格雷斯的结构概念，包括转换单元，正式参数单位，转换模块，以及它们的组成模块化系统。1介绍潜在地，图变换构成用于建模信息处理系统的基于规则的框架，信息三卷的《图文法和图变换计算手册》[18，4，5]提供了这一事实的一些证据。然而，图变换既不是一般已知的，也不是在广泛的应用中经常使用的。为了提高图形转换的可见性和实用性，来自柏林、不来梅、埃尔兰根、慕尼黑、奥尔登堡和帕德尔-博恩的一组研究人员几年前开始开发以图形和规则为中心的建模语言Grace（参见[1，2，10，12，13，14，15，17，19]）。恩典的主要思想和目的如下。方 法独立性：用户可以根据自己的需要和品味选择自己喜欢的图形、规则、规则应用程序等。这（至少在理论上）是通过图变换方法的一般概念来实现的。结构化：为了支持从小型可重用组件开发大型图转换系统，？ 本研究得到了EC TMR网络GETGRATS（图形转换系统的一般理论）和ESPRIT基础研究工作组APPLIGRAPH（图形转换的应用）的部分支持。c2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2G的g0G00桥加法A BHPHP专用HC是/否是/否是/否Fig. 1. 在运行示例包括转换单元、形式参数单元、转换模块和模块组合。形式语义：所有概念的语义都是基于规则应用程序给出的图上的二元关系来形式化定义的。当变换单元计算图上的单个关系时，形式参数单元以松散的方式描述一类关系。由于转换模块封装了一组转换和形式参数单元，因此它从其成员单元中获得其含义验证：因为语义是建立在规则应用程序的顺序组合的迭代上，所以归纳原理可用于证明图上建模关系的属性。这是未来验证和解释工具的关键。可 视 化和动画：图形界面计划用于编辑和评估转换单元和模块。通过这种方式，在Grace中建模的模块化图转换系统将被可视化和动画化（参见Martin Faust的GRACEland[7]以获得非常早期的原型）。在本文中，我们概述了恩典的思想和目标，第一个三点。为了说明所讨论的概念，我们提出了一个运行的例子，这是NP问题的减少的概念的启发明确地说，我们认为NP完全问题HC，HP和HP特殊。rst是对哈密尔顿循环的测试（即，一个周期访问每个节点正好一次），第二个是对哈密尔顿路径的相应测试，第三个是对两个不同节点A和B之间的哈密尔顿路径的测试。众所周知，HP可以使用多项式变换（称为add-A Bresp）约化为HPspecial，并且这约化为HC 图1中的桥。我们将HC、add-A、B和网桥建模为转换单元，并使用后两者构建了两个转换模块。然后通过模块组合得到图1中的示意图。虽然这个例子很小，但它可以给你一个结构化建模的机会。2图变换方法图是非常通用的结构，用于数十种变体，类型和模式。因此，人们会遇到相当多的竞争图3一0在文献中的转换方法。因为优雅的结构概念以相同的方式适用于其中的大多数（如果不是全部），我们认为图变换是一个统一的和方法无关的框架。这是通过图变换方法的抽象和公理化概念来实现的，该方法可以被实例化，但是它可能是适当的。图变换方法提供一类图、一类规则和规则应用操作符，该规则应用操作符指定如何通过应用规则从图直接导出图。由于规则定义了图上的二元关系，因此规则集将导出关系指定为规则应用关系的并集的自适应和传递闭包。此外，图转换方法提供了限制规则应用程序及其迭代的不确定性的方法形式上，图转换方法由图的类G、规则的类R、产生二元关系的规则应用操作符（例如，图的类G和规则应用操作符R））r GG，一个G类表达式类E，使得每个e2E指定一个子类SEM（e）G，一个控制条件类C，使得每个c2C指定一个二元关系SEM（c）G G.图类的例子有标记的有向图，超图，树，森林，nite自动机，Petri网等。规则类可以从更严格的，如边缘或节点替换，到更一般的，如双推出规则，单推出规则或进度规则。一般来说，规则应用运算符描述了R中的规则如何应用于G中的图。控制条件用于调节推导过程。例如，它们确定规则的应用顺序（请参见例如[16]）。图类表达式的目的是将图的集合限制为这些特定规则可以被应用或筛选出可以由一组规则导出的所有图的子集。典型地，图类表达式可以是描述图属性的某个逻辑公式，如连通性、或非循环性、或某些节点或边标签的出现或不存在。在运行的示例中，使用无向图，其中每个节点可以携带任意数量的ags。例如，图中的节点有两个标记为A和0的标记。示例中使用的规则类型相当直观：规则由左侧图和右侧图组成，其应用意味着将左侧图的出现替换例如，可以添加一个节点（使用ag），添加一条边，或删除一个ag。正则表达式被用作控制条件，并解释了图类表达式的含义。4R桥姓名首字母缩写：A B-标记规则：r：！终端：不加标签的B一添加-0-ags姓名首字母缩写：不加标签的规则：r：！终端：全0标记03变换单元转换单元是grace的主要语法实体，它允许在图上指定二元关系。它们由规则、输入、输出和控制条件以及输入组件组成。在语义上，转换单元导入与规则应用交错的图上的二元关系，使得输入、输出和控制条件满足。以这种方式，变换单元封装计算过程。由于它指定了图上的二元关系，因此可以通过其他转换单元导入，因此该概念以简单但有效的方式支持结构化。设A=（G;R;）;E;C）是一个图变换逼近。A上的变换单元是一个系统tu =（I; U; R; C;T），其中I和T是图类表达式，U是一组标识符，R是一组规则，C是一个控制条件。 SEM（I）的元素称为初始图，SEM（T）的元素称为终端图。U是tu的导入组件，也称为使用组件。设SEM（t）GG是图上的某个二元关系，且对每个t2U，SEM（U）是这些关系的并.然后，由y（）[SEM（U））\SEM（I）SEM（T）\SEM（C）来定义t的交织语义SEM（U）;即，当满足控制条件时，通过交错规则应用和输入关系的调用来关联初始图和终端图作为示例，我们提出了四个变换单元。前两个，bridge和add-0-ags，有一个空的use组件，没有控制条件。B-标记和非标记是常量图类表达式，后者指定所有没有标记的图，而前者指定所有具有唯一A标记节点、不同唯一B标记节点且没有进一步标记的图。给定这样一个初始图，唯一的规则可以应用一次，删除A-和B-标签，并在两个不同的节点之间建立一个桥梁。应用add-0- ags的唯一规则，0- ags可以添加任意次数，但是只有每个节点都有唯一0-ag的图才被接受为终端图，因为常量图类表达式all-0- agged需要。单元add-A B的控制条件声明首先调用导入的单元add-0- ags，它获取任意未标记的图并向每个节点添加0-ag然后应用规则r1一次，添加一个新的A-5HC用途：添加-0-ags规则：r1：！r2：！规则三：！规则四：！第二：add-0- ags;r;r;r;r1 234终端：不加标签的开始运行运行0运行运行开始0开始开始0加法A B用途：添加-0-ags规则：r1：;！r2：！一1r3：;！规则四：！B第二：add-0- ags;r;r;r;r1234终端：未-0 j1-标记1BB0一一标记节点。之后，规则r2可以任意频繁地应用。这将连接带A标记的节点和带0标记的节点，同时ag从0变为1。那么r3必须被应用，添加一个新的B-标记节点。 最后，只要你喜欢，R4就可以应用。 graph类表达式not-0 j1- agged禁止具有0-或1- ags的图，使得只有所有原始节点与两个新节点连接的图是终端。最后，单元HC在其初始图中的每一个中搜索哈密尔顿圈。导入的单元将0- ags添加到未标记的图中，并且规则更改并删除ags。 由于要求终端图是无标记的，HC的语义关系的元素是相同的图对（G; G）。从这样一个G开始，add-0- ags将0-ag添加到每个节点。 其中一个被改变为由r1启动，并且一个neig hborn ode的ag被改变为由r2运行。然后重复r3，其中run- ag沿着边遍历图并消耗0-ags。最后，应用r4，关闭一个循环并消耗run和start。如果没有0-ag，这个循环访问G的每个节点一次，这意味着G是哈密尔顿的。如果一个图不是哈密尔顿图，则不能用这些规则去掉所有的0-ags因此，可以将HC视为对Hamilton图的测试。60 004形式参数单位转换单元的语义关系是唯一确定的，取决于所使用的单元的语义。换句话说，交织语义是功能性的，这意味着必须完全定义变换单元的所有组件。然而，在发展的中间阶段，人们可能更喜欢留下一个规范的部分不完整，或者一些构造可能适用于各种变换单元，因此留下一个规范变量的部分可能是值得的。这两种方法都可以通过形式参数单位的概念来实现.形式参数单位定义了图上的一类关系。通过将变换单元分配给形式参数单元，可以从（也许许多）可能的关系中选择特定的关系。形式参数单元由名称FORMAL和要求符组成，写作FORMAL =EQUIPMENT ， 使 得 EQUIPMENT 具 有 松 散 的 图 转 换 语 义 LOOSE（EQUIPMENT），这是图上的一类二元关系。 如果SEM（tu）2LOOSE（），则转换单元满足要求。此外，另一个形式参数单元FORMAL = saties if LOOSE（）LOOSE（）。至少有两种重要的需求提供了有用的形式参数单元。首先，可以通过对关系的全局要求（如总体性、内射性、满射性、功能性等）来限制图上所有二元关系的类。作为默认要求，可以使用none，这意味着没有限制，形式参数单元是任何实际单元的占位符。其次，该要求可以由图上的二元关系SEM（ C1）和SEM（C2）的两个集 合 的 一 对 （ C1;C2）组成，其服务于上下界，即， LOOSE（（C1;C2））包含所有关系R，使得SEM（C1）RSEM（C2）。在图上指定二元关系的典型方式是描述输入/输出关系SEM（I）SEM（T）的（初始和终端）图类表达式对I T另一种可能性是使用逻辑公式，特别是一元二阶公式，它使用节点、边、节点集、边集、成员、包含和通常的布尔连接词来描述图上的二元关系。当然，下界和上界关系也可以被指定为变换单元。形式参数单元的另一个更具体的例子是A B- agged-initials=initialis A B- agged：图的一个二元关系满足A B-凸首字母如果到第一个组件上的投影是SEM的子集（A B- agged），其中A B-agged是上一节中介绍的图形类表达式。同样，参数单元un agged-initials=初始化为未标记7作为松散的语义承认所有的关系，其中到第一个组件的投影是SEM（未标记）的子集例如，HC关联未标记的图，使得SEM（HC）2LOOSE（未标记的首字母缩写）。这两个例子都是形式参数的上下界类型的特殊情况，以空关系作为下界。5变换模块虽然变换单元的概念允许使用其他单元，但每个单元都指定了图上的单个二元关系。然而，通常希望将逻辑上属于一起的几个关系这导致了图变换模块的概念，具有导入和导出接口并且可以提供多于一个二元关系的模块，即，他们有一套关系供别人使用在本节中，转换模块的概念被引入为一组转换单元的封装。 模块的单元可以是通过使用模块的其他单元来定义，如果该单元在环境中是已知的，则可以导入它，或者它可以是松散指定的形式参数，并且可以稍后实例化。那些公开可用的单元属于模块的导出接口。如果限制考虑模块的层次，非循环使用结构的单元，模块的语义可以直接从变换单元的交织语义。语义根据形式参数将语义关系与模块的每个单元相关联。转换模块MOD由导入接口IMPORT、形式参数PAR、主体BODY和导出接口EXPORT组成。IMPORT是一组标识符，表示环境中已知的单元，PAR是一组形式参数单元，BODY是由模块定义的一组转换单元，EXPORT是BODY[IMPORT[PAR]的子集，提供了模块中公开可用的那些单元此外，假设每个主体单位仅使用BODY、IMPORT和PAR单位。请注意，与指定图上的一组二元关系的形式参数相反，导入部分由模块环境中可用的完全指定的转换单元的名称组成在实践中，进口物品可以由其他转换模块，例如Modula-2。转换模块的定义的后一个条件允许将模块的使用结构描述为具有BODY、IMPORT和PAR的单元（的标识符）作为节点并且具有从v到v0的边的 whene verv0使用，使用在下文中，我们将我们的考虑限制为具有非循环使用结构的模块，因为在这种情况下，模块的语义可以沿着其使用结构来定义。首先，给出了导入单元的语义关系，对于8还原-1进口：加法A B参数：首字母A B主体：减少-1第二： add-A B;首字母A B出口：减少-1还原-2进口：桥参数：非重叠首字母主体：出口：减少-2第二：桥梁;非重叠首字母减少-2每个形式参数单元选择其松散语义的一个关系。然后重复以下过程：如果所有使用的单元都已经具有语义关系，则单元获得其交织语义。步骤的数量由使用结构中的最长路径的长度限制。特别地，每个导出的单元根据实际参数的选择来定义语义关系。如果形式参数为空，则模块的语义被唯一地确定为每个导出单元的语义关系。这样的模块被称为完全指定的。如果想要将具有非空形式参数的模块转换为完全指定的模块，则可以使用其他模块的导出单元来实例化形式参数单元。下一节将详细讨论这种模块组合在下面的两个模块示例中，导出的单元顺序地组成具有唯一参数单元的唯一导入单元。此外，请注意，如果将使用组件作为导入，将单元本身作为主体和导出，则每个转换单元都可以被认为是一个关于具有和不具有循环使用结构的模块的转换单元网络的语义的更多信息可以在[14，15]中找到。6模块组成模块的组合类似于[6]意义上的模块规范的部分组合，通过连接模块的组件并将形式参数单元替换为相应的实际单元来产生组合模块，只要形式参数出现在主体中。模的组合原来是结合的。作为一个很好的结果，模块系统可以用图形的方式表示，其中基本模块作为节点，并且是900000000一a0级一00MOD00MOD0MOD一个模块具有另一个模块的一些输出单元作为边缘。如果没有形式参数单元被实例化两次，并且模块结构是非循环的，则这种模块结构设MOD和 MOD是两个模块，设a是 MOD的一些形式参数单元到 MOD的导出单元的部分赋值映射，使得对于a的域dom（a）中的每个形式参数单元 par，移植单元A（PAR）满足PAR的要求。 然后，MOD和 MODa到a由MOD表示！MOD并产生了模，导入接口IMPORT[IMPORT]、形参（PARrdom（a））[PAR]、主体insta（BODY）[BODY]和导出接口insta（EXPO RT）[EXPO RT]的规则。 除了在所有组件中取并集之外，该组合还从形式参数中删除了部分赋值a的定义域，表示为PAR r dom（a），并将BODY和EXPORT中所有出现的dom（a）单元替换为相应的单元，分别表示为insta（BODY）和insta（EXPO RT）。这个复合的一个有趣的特例是完全未知的赋值。在这种情况下，复合只是按分量的联合。组合的目的是用实参数单元实例化形式参数单元，从而通过一系列组合，将具有非空形式参数的给定模块转换为完全指定的模块。为了实现这一点，每个形参单元最终都必须被实例化。实例化的结果仅取决于实际参数的选择，而不取决于实例化的顺序。这是因为观察到模块的组成是关联的，即，连续的合成可以以任何顺序进行，具有相同的结果。更正式地说，如果a a0（MOD！ MOD0）！定义了MOD00，则有赋值b和b0 苏志华B这个MOD！（国防部b0的！MOD）的定义，并等于前者的组成。反之亦然。在这两种组合中，相同的形式参数单元被分配给相同的扩展单元，即，a等于b，在dom（a）上，a等于b 在do m（b0）和a0上在MOD的形式参数单位上等于b，其中ch是用MOD的导出单位实例化的。如果后一种分配由00表示，则组合物a bove以以下图形方式唯一地表示：这一观察有一个很好的结果。图变换系统可以以图形形式被指定为具有部分分配作为边的模块的网络。如果网络是非循环的，并且没有形式参数单元被实例化超过一次，则可以通过组合将其转换为转换模块，这为网络提供了形式语义组合序列的导出接口是所涉及模块的所有导出接口的联合，直到一些重命名。这是有用的，如果0000010一一HC，insta（还原-2）出口：HC，insta（还原-2）主体：桥接，添加-0-ags进口：一减少-2！HCHC，HP专用，仪表b（减少-1）出口：HC，HP专用，仪表b（减少-1）主体：add-A B，桥接，add-0-ags进口：B减少-1！降HP专用 HC导出的单位应可用作实际参数，但最后可能需要隐藏其中的一些。这可以通过伴随组合的另一个模块构建操作来实现：允许将模块的导出接口限制为子集的导出限制如上所示，变换单元HC涉及未标记的图并且因此满足未标记的首字母的要求。因此，成分减少-2！还原2的HC和HC（如第5节末尾所述，由单元HC构建）使用实例a定义，其中a（unagged-initials）= HC，并产生以下变换模块。我们可以很容易地证明，由Bridge指定的变换与Hamilton图检验的组合是对每个初始图的A-标记节点到B-标记节点的Hamilton路的存在性的检验。 因此，我们将inst a（ reduced-2） 重命名为HP special和reduction-2！HC转换为HP降低专用HC。由于bridge将SEM（AB&-标记）中的图变换为无标记的图，所以HP特殊语义关系在第一个成分上的投影满足AB&-标记声母的要求。因此，使用具有b（A& B-聚集首字母）= HP special的实例b，定义了还原-1和HP special到HC的还原的组成，并产生以下模块。我们可以很容易地证明，&add-AB和HP special的组合给出了G中Hamilton路存在性的一个检验。因此，可以将inst b（reduced-1）重命名为HP，将整个模块重命名为reductions-of-HP-to- HP special-to-HC。请注意，此模块对应于图1中显示的情况。此外，通过模块组合的结合性，11得到相同的结果，如果rst模块reduction-1和reduction-2被组合，并且所得到的模块然后被HC实例化。7结论本文简要地概述和说明了地理空间的结构概念。在文献中，人们提出了图变换系统的一些进一步的构造原则（见[3，8，9，11，20，21]），并与[2]中的grace概念进行了比较（也见[9]）。虽然已经详细研究了转换单元（网络）的交织语义以及简单转换模块的交织语义，但未来的研究将不得不更多地阐明优雅方法作为一个整体的意义(i) 转换模块的实例化和组合需要进行彻底的调查，而不仅仅是上面概述的最初考虑。(ii) 尽管到目前为止，所有的示例都非常小，但案例研究对于证明这些概念对大型系统建模的有用性(iii) 一个非常有趣的问题是结构化建模如何一方面支持验证，另一方面支持可视化和动画对这些和其他主题的研究可能会受益于实验工具的实施，这些工具允许人们玩弄恩典的特征，看看会发生什么，正如恩典之地在这 个 方向 上 的 第一次 尝试所表明的那样。总而言之，在图形转换系统建模方面还有很长的路要走。 让我们一起干吧。引用[1] Andries，M.， G. Engels，A. 哈贝尔湾 何曼，H.- J. Kreowski，S. 库斯克，D. Plump，A. 史昌湖rr和G. 陈文辉，计算机程序设计与应用，北京大学出版社，1999年。1{54.[2] Drewes，F.，P. Knirsch，H.- J. Kreowski和S.图的变换模及其构造，见：M. Nagl，A. 史昌湖rr和M. 微米的n ch，编辑，Proc.Applications of GraphTransformations with Industrial Relevance ， LectureNotes in ComputerScience1779，2000，pp. 15{30.[3] Ehrig，H.和G.图转换系统的模块概念的语用和语义方面，在：J.E. Cuny，H. Ehrig，G.恩格斯和G. Rozenberg，编辑，Proc. Fifth Intl.图形文法及其在计算机科学中的应用研讨会，计算机科学讲义1073，1996，pp。137{154.[4] Ehrig，H.，G.恩格斯，H. J. Kreowski和G. 林文龙，《计算机图形学与图形转换》，第二卷：应用、语言与工具，《世界科学》，1999年。12[5] Ehrig，H.，H.- J. Kreowski，U. Montanari和G.罗曾柏，编辑，《图形文法手册与图形转换计算》，第3卷：并发、并行与分布，《世界科学》，新加坡，1999年。[6] Ehrig，H.和B.李文，《计算机科学与工程》，北京：清华大学出版社，1990。[7] Faust ， M. ， GRACEland 网 页 ， URL ： http://www.informatik 。 uni-bremen.de/theorie/GRACEland（1998年）。[8] Gro e-Rhode，M.，F. Parisi Presicce和M. Simeoni，类型化图变换系统的元素和模块，在：代数开发技术研讨会，计算机科学讲义1589，1999，pp.137{151.[9] 赫克尔河，G. Engels，H. Ehrig和G. Taentzer，图变换系统的模块概念的分类和比较，在：Ehrig等人[4]，pp. 639{689.[10] 赫 克 尔 河 ， B. Ho mann ， P.Knirsch 和 S.Kuske ， Simple modules forGRACE ， in ： H.Ehrig ， G. 恩 格 斯 ， H.J. Kreowski 和 G.Rozenberg ，editors，Proc.图变换的理论与应用，计算机科学讲义1764，2000年，页。383{395.[11] 卡普兰，S。M.，J. P. Loyall和S. K. Goering，用- Grammars描述并发语言和系统，在：H。 Ehrig，H.- J. Kreowski和G. Rozenberg，编辑，Proc.Graph Grammars and Their Application to Computer Science，Lecture Notesin Computer Science532， 1991，pp. 475{489.[12] Kreowski，H. J.，G. Busatto和S. Kuske，GRACE作为统一的方法到基于图变换的规范，在：Proc.图形过程规范技术的统一方法，理论计算机科学电子笔记44（2001）。[13] Kreowski，H. J.和S. Kuske，Graph transformation units and modules，in：Ehrig et al.[4]，pp. 607{638.[14] Kreowski，H. J.和S. Kuske，Graph transformation units with interleavingsemantics，Formal Aspects of Computing11（1999），pp. 690{723.[15] 克雷奥斯基J.，S. Kus ke和A. 史昌湖rr，Nestedgr aphhtransformationunits，International Journal on Software Engineering and Knowledge Engineering7（1997），pp. 479{502.[16] Kuske，S.，更多关于变换单元的控制条件，在：H.埃里希G. 恩格斯，H. J. Kreowski和G. Rozenberg，编辑，Proc.理论和图变换的应用，计算机科学讲义1764，2000，pp. 323{337.13[17] Kuske，S.，图变换系统的结构化概念”，博士。论文，不来梅大学（2000年）。14[18] 罗森伯格，G.，编辑，\Handbook of Graph Grammars and Computing byGraph Transformation，Vol.1：Foundations，”World Scientic，Singapore，1997。[19] 史昌湖rr，A.，GRACE 中的图形转换和图形转换单元，J.E. Cuny，H.Ehrig，G. Engels和G. Rozenberg，编辑，Proc. Graph Grammars and TheirApplication to Computer Science，计算机科学讲义1073，1996，pp. 122{136.[20] 史 昌湖rr ， A.和 A.J.Wi nter ， UML 包 在 P RO g ram m e d Gr apREwritingSystems中的应用，H. Ehrig，G.恩格斯，H. J. Kreowski和G.Rozenberg，编辑，Proc.理论和图变换的应用，计算机科学讲义1764，2000，pp. 396{409.[21] Tae ntzer，G. 和A. 史昌湖rr，DIEGO，在图变换系统的概念上又迈出了一 步 ， A. Corradini 和 U. Montanari ， editors ， SEGRAGRA'95 ， JointWEBGRAPH/SEMAGRAPHWorkshoponGraphRewritingandComputation，Electronic Notes in Theoretical Computer Science2（1995）.
我的内容管理
展开
