期刊文献+

基于矩阵运算的图转换检测算法 被引量:1

Graph transformation detecting algorithm based on matrix operations
下载PDF
导出
摘要 本文基于图是一种可以把复杂的问题直观地表示出来的自然的方式,已应用于计算机科学的几乎所有方面,从而图转换系统(GTS)得到了广泛的用,但是在图转换系统中不同的规则复合会产生冲突,想通过计算机系统自动判断不同规则能否复合,减少规则复合人工干涉这一目的,采用了矩阵运算的方法,并且定义冲突矩阵,关联矩阵以及规则链等概念,将各个规则看作各个规则的节点,这样就形成一个有向的规则链。记作pi→pi+1→…→pj,计算各个规则链长度的方法,得到了个规则节点到其他节点的长度,通过寻找复合规则之间长度为l的规则链是否存在,从而检测出这一系列规则有无冲突。 The paper is based on the mothed which a complex problem can be expressed directly in the natural way by the graph, it has been used in almost all aspects of computer science.The graph transformation system (GTS) has been widely used, but different rules in the graph transformation system may conflict. Whether it determine the different rules have conflict by automatic computer system, it reduce the human intervention between the compound of different rules. It use the matrix operations and define the notions of conflict matrix, correlation matrix, the chains of rules, which think the rule as a node. There is a direction rules chains pi→pi+1→……→pj the length of the chains can be calculated. It can determine whether the different rules have conflict by looking for the existence of chain which the length is l. According to the relations between the compound of rules and matrix operations, a automatic graph transformation systems detecting algorithm is put forward.
作者 朱跃龙 陈亮
出处 《电子设计工程》 2011年第5期67-70,共4页 Electronic Design Engineering
基金 国家科技支撑计划资助项目(2008BA29B03) 河海大学自然科学基金项目(理科类)(2008432311)
关键词 图转换 矩阵运算 规则链 冲突矩阵 关联矩阵 graph transformation matrix operations the chains of rules conflict matrix correlation matrix
  • 相关文献

参考文献9

  • 1Ehrig H,Prange U,Ehrig K. Fundamentals of Algebraic Graph Transformation [M]. EATCS Monographs in TCS,2006.
  • 2Corradini A, Ehrig H, Montanari U,et al. Conflict detection for graph transformation with negative application conditions [J]. the 3rd Int'l Conf. (ICGT 2006). LNCS 4178, 2006: 61-76.
  • 3Corradini A,Montanari U,Rossi F,et aL Algebraic approaches to graph transformation:basic concepts and double pushout approach [M]. Handbook of Graph Grammars and Computing by Graph transformation,Volume 1: Foundations. World Scientific, 1997.
  • 4Mens,T.On the use of graph transformations for model refa- ctoring [M]. Generative and Transformational Techniques in Software Engineering, LNCS 4143, 2006.
  • 5Mens T, Van Eetvelde N, Demeyer S,et al. Formalizing refactorings with graph transformations[J]. Journal on Software Maintenance and Evolution, 2005,17 (4) : 247-276.
  • 6Habel A, Hoffmann B. Parallel independence in hierarchical graph transformation [M]. ICGT 2004.
  • 7Taentzer T G, Runge O. Detecting structural refactoring conflicts using critical pair analysis [J]. Electronic Notes in Theoretical Computer Science, 2005 : 127-113.
  • 8Detlef Plump. Critical pairs in term graph rewriting[J]. Math- ematical Foundations of Computer Science, i994:113-117.
  • 9Mens T. A formal foundation for objeeboriented software evolution [D]. Department of Computer Science, Vrije Unive- rsiteit Brussel, 1999.

同被引文献2

引证文献1

二级引证文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部