参数化变换单元：图变换系统的构造原则

网址：http://www.elsevier.nl/locate/entcs/volume51.html12页参数化变换单元萨宾·库斯克不来梅大学计算机科学P.O. Box 330 440，D-28334 Bremen，Germany摘要变换单元是图变换系统的构造原则。它们由一组图变换规则、初始图和终止图的描述、控制条件和一组导入的变换单元组成。从语义上讲，它们通过将规则应用与对导入单元的调用交错，将初始图转换为终端图，为了以一种可管理的、简洁的方式描述大类的相似变换单元，我们对变换单元进行了形式参数扩展。参数化转换单元的组件是包含类型化变量作为参数的类型化表达式。 结果表明，参数化变换单元的参数实例化再次产生参数化变换单元并且是关联的。1介绍图变换构成了一个深入研究的领域，具有许多潜在的应用领域，如可视化语言，分布式系统规范，数据库系统，定理证明，函数式编程语言，抽象数据类型等（参见[19，5，6]的概述）。虽然在图变换领域存在着各种不同的方法，但它们都依赖于同一个共同的范式：通过将规则应用于图来变换图，并且将规则应用于图再次产生图。基于图变换系统的实际应用可能由非常大的规则集组成。如果没有可用的结构化原则，它们很难管理。出于这个原因，在过去的十年中，已经提出了用于图转换的各种模块化概念，例如平台[11]，gspec模块[4]，转换单元[15，18]，？ 这项工作得到了ESPRIT工作组图形转换应用（APPLIGRAPH）和EC TMR网络GETGRATS（图形转换系统通用理论）的部分支持。c2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2[23] 2016 年 10 月 23 日 ， 中 国 国 际 航 空 航 天 博 览 会 [8]packages[2 2]和transformationmodules [14，3，10]，其中后者允许对transformationunit进行聚类。其中，绝大多数人都是在“九”字中找到的。除了gspec模块、转换单元和转换模块之外，它们都依赖于特定的图转换方法。这意味着，粗略地说，它们只能构造其规则属于特定类型的转换系统。本文提出了变换单元的概念，并将其推广为形式参数。更详细地，变换单元由一组图形变换规则、初始和终端图形的描述、控制条件和一组导入的变换单元组成。它的语义是交错的，因为它通过以满足控制条件的方式将规则应用程序与对导入单元的调用交错来将初始图转换为终端图。转换单元是图和规则中心语言的基本组成部分，目前正在柏林，不来梅，埃尔兰根，慕尼黑，奥尔登堡和帕德博恩开发（参见[13，1，20，12]）。值得注意的是，由于它们的方法独立性，转换单元也可以用作依赖于图以外的其他对象的基于规则的系统的结构原理[16]。为了能够以可管理的和有限的方式描述大类的类似变换结果表明，参数化变换单元的参数实例化再次产生参数化变换单元并且是关联的。2变换单元变换单元独立于特定的图变换方法。这意味着基本组件，如规则、图类描述和控制条件由图转换方法提供。在下文中，我们假设ID表示标识符的任意但固定的集合（其用于规则和变换单元的名称）。定义2.1（图变换方法）图变换方法是系统A=（G;R;）;C;E），其中G是一类图，R是一类规则，）是一个规则应用运算符，对于每个r 2 R产生一个二元关系）rGG，C是一类控制条件，使得每个C2C指定一个二进制3R关系式SEM E（C）GG为每个映射E：ID！2G G，1和E是一类图类表达式，使得每个X2E指定一个集合SEM（X）G.注意，控制条件可以包含标识符（其指的是变换单元或规则）。因此，它们的语义取决于它们的环境E，环境E将语义关系与每个这样的标识符相关联在变换单元的上下文中，引用局部规则r的标识符的语义等于t，并且引用导入的变换单元t的标识符层的语义是t的交织语义。图变换方法的一个例子是（G;R;）;C;E）， 其中G是所有有向标记图的类。所有标签都是label类型，由integer和string子类型组成。为了下面的明确使用，术语选择所有节点（G）与G2G表示通过用s标记的环标记G中的每个节点而从G获得的图。(The标签s代表选定。）类R和规则应用操作符）的定义与双推出方法[2]相同。 这意味着规则具有r =（L; K; R）的形式，其中L、K和R是图，K是L和R的子图。直觉，）通过应用以下步骤从图G导出图G 0（更多细节参见[2]）。（1）在G中选择L的一个图像。(2)检查一些特殊的应用条件，称为胶合条件。（3）从G中去除L的像（直到K的像）。（4）通过将R的子图K粘到K的像上，将R添加到剩余图。控制条件类C由ID上的所有正则表达式加上条件once（id）和id！对于每个ID2ID。每个正则表达式C规定了规则或转换单元可以应用的顺序这意味着，直观地说，如果id1 idn是C语言指定的一个单词，那么id1;：;idn可以按此顺序应用。条件once（id）允许所有id只应用一次且id！尽可能长时间地使用ID除了默认表达式allwithSEM（all）= G之外，类E包含单个图，并且表达式没有s-循环。对于每个G2 G，SEM（G）=fG g.此外，SEM（nos-loop）是由所有没有s-标号环的图组成的一个变换单元由一组导入的命名变换单元、一个初始图规范、一组命名局部规则、一个控制条件和一个终端图规范组成。值得注意的是，我们考虑具有非循环导入结构的转换单元。在[17]中研究了具有任意输入的变换单元定义2.2（T转换单元）。设A=（G;R;）;C;E）是一种图变换方法.然后A上的变换单位的集合TU被归纳地定义如下。 对于所有的I，T 2 E，C 2 C和集合R1对于集合A，2A表示它的幂集。4E（tu）命名规则，即 部分映射R：ID！R：(i) （I;R; C;T）2TU，输入深度（（I;R; C;T））= 0：(ii) 对于每个部分映射U：ID！对于每个id，具有导入深度（U（id））

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