Syntax Definition with Graphs

Syntax definition of visual languages is required for a precise definition of a visual language; it is a requirement for the automatic creation of tools that process diagrams of the language. This paper describes a lecture together with an exercise which have been given by the author at the SegraVis Summer-School at Schloss Dagstuhl, Germany, in May 2004. The paper presents in a tutorial like way the DiaGen approach of defining visual language syntax with hypergraphs and hypergraph grammars.     

A graph-based algorithm for consistency maintenance in incremental and interactive integration tools

Development processes in engineering disciplines are inherently complex. Throughout the development process, the system to be built is modeled from different perspectives, on different levels of abstraction, and with different intents. Since state-of-the-art development processes are highly incremental and iterative, models of the system are not constructed in one shot; rather, they are extended and improved repeatedly. Furthermore, models are related by manifold dependencies and need to be maintained mutually consistent with respect to these dependencies. Thus, tools are urgently needed which assist developers in maintaining consistency between inter-dependent and evolving models. These tools have to operate incrementally, i.e., they have to propagate changes performed on one model into related models which are affected by these changes. In addition, they need to support user interactions in settings where the effects of changes cannot be determined automatically and deterministically. We present an algorithm for incremental and interactive consistency maintenance which meets these requirements. The algorithm is based on graphs, which are used as the data model for representing the models to be integrated, and graph transformation rules, which describe the modifications of the graphs to be performed on a high level of abstraction. This paper is an extended version of [6].     

From model transformation to incremental bidirectional model synchronization

The model-driven software development paradigm requires that appropriate model transformations are applicable in different stages of the development process. The transformations have to consistently propagate changes between the different involved models and thus ensure a proper model synchronization. However, most approaches today do not fully support the requirements for model synchronization and focus only on classical one-way batch-oriented transformations. In this paper, we present our approach for an incremental model transformation which supports model synchronization. Our approach employs the visual, formal, and bidirectional transformation technique of triple graph grammars. Using this declarative specification formalism, we focus on the efficient execution of the transformation rules and how to achieve an incremental model transformation for synchronization purposes. We present an evaluation of our approach and demonstrate that due to the speedup for the incremental processing in the average case even larger models can be tackled.

Analysis and generation grammars

This paper describes the analysis and generation grammars for English and Japanese as they were employed in the KBMT-89 program. We discuss word order, coordination, subcategorization, morphological rules, rule ordering and bi-directional grammars.     

面向对象的图可视化系统设计与实现

阐述了一个小型图可视化系统的设计原理及方法。系统采用面向对象的方法设计并按照信息可视化模型分层架构,具有良好的可扩展性。系统支持随机布局、弹力模型、对称[1]等多种图形布局方式;并提供了对GML、DAT、TXT、自定义等多种图形数据封装格式的存取功能。     

The Grasper-CL graph management system

Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in COMMON LISP and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL graphs can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL employs a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.     

含假结RNA二级结构类的图语法

用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。     

Remarks on some aspects of language structure and their relevance to pattern analysis

Some specific aspects of language structure are examined in detail in the context of pattern analysis. In particular, a transformational grammar is constructed for a class of patterns, following the linguistic formulation very closely, by taking a simple example and working it out in detail. Many of the characteristics of the transformational grammars of linguists show up even in this simple example. The need for looking for grammars of different styles and the problem of making meaningful assignment of probabilities to sentences in the context of transformational grammars have also been briefly discussed.     

异构图形数据的近似语义匹配技术研究

以流程工厂协同设计应用为背景,提出基于允许误差的最大语义图匹配（MSMGE）算法的异构图形数据近似语义匹配模型。利用类无向图来描述2D和3D异构图形数据的工程属性和拓扑关系,消除了图形信息的异构性,并建立各种类实体的属性标签词典来消除2D和3D属性信息的异构性,用语义表达式来表示类无向图顶点和边的语义关系,将异构图形匹配转化为近似语义图匹配。通过基于工程语义对类无向图进行语义分割和基于最大公共序列算法的语义表达式比较、语义规整和语义裁剪等方法,降低了匹配搜索空间,提高了近似语义图匹配效率,实现了近似语义图匹配判断。该研究已经在流程工厂设计软件中得到较好地应用。     

A syntax-directed program that performs a three-dimensional perceptual task

A syntax-directed program that performs a three-dimensional perceptual task is described. The task, in a slightly simpler form, was used originally in a psychological study of mental rotation. ⁽¹⁾ The task consists of determining whether two line drawings portray (different views of) identical objects, mirror image objects, or structurally different objects, where the objects are composed of linear strings of attached cubes. The program is syntax-directed in the sense that it uses a fixed set of syntactic rules to analyze the line drawings. This is the first use of formal syntactic techniques in the analysis of pictures (in this case, line drawings) of three-dimensional objects.     

On the languages generated by context-sensitive fuzzy grammars

It is proved that the family of the languages generated by 1-fold fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is equal to the family of the context sensitive languages. Also, one shows that the family of the languages generated by fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is included in the family of the context-sensitive languages.     

A microcomputer-based pallet layout system to evaluate and improve storage space utilization

This paper discusses a microcomputer-based system used to maximize the storage space utilization for palletized materials. Pallet and carton sizes and stacking constraints for specific stock numbers are used to compute and select the best layout from several possible alternatives. The results, giving the simplest stable layout, are converted to graphic form and printed on a dot-matrix printer for use by Engineers and Warehouse personnel in evaluating and improving storage space utilization.     

基于多层次随机梯度下降的大规模图布局算法

大规模图布局问题是图可视化领域研究热点之一.应力布局模型在保持全局布局结构方面表现出色,然而其求解速度却不及弹簧电荷模型,且局部布局质量也有所欠缺.在维持全局结构稳定条件下,为提高应力模型求解大规模图时的布局速度、改进布局局部结构表达,提出了一个新的多层次随机梯度下降图布局模型..首先利用基于邻居结构的图压缩合并算法生成层次图结构,再使用节点最优放置算法初始化节点坐标.最后利用融合了节点正负样本的随机梯度下降算法细化布局,改进局部布局质量.同时多层次方法也有效提高了布局速度.在30个不同规模的数据集上与现有布局模型进行对比实验,从布局计算效率、布局质量以及可视化效果三个方面证明了该方法的有效性.     

Tool Integration with Triple Graph Grammars - A Survey

Nowadays, typical software and system engineering projects in various industrial sectors (automotive, telecommunication, etc.) involve hundreds of developers using quite a number of different tools. Thus, the data of a project as a whole is distributed over these tools. Therefore, it is necessary to make the relationships of different tool data repositories visible and keep them consistent with each other. This still is a nightmare due to the lack of domain-specific adaptable tool and data integration solutions which support maintenance of traceability links, semi-automatic consistency checking as well as update propagation. Currently used solutions are usually hand-coded one-way transformations between pairs of tools. In this article we present a rule-based approach that allows for the declarative specification of data integration rules. It is based on the formalism of triple graph grammars and uses directed graphs to represent MOF-compliant (meta) models. As a result we give an answer to OMG's request for proposals for a MOF-compliant “queries, views, and transformation” (QVT) approach from the “model driven application development” (MDA) field.