嵌入一致图语法的依赖图

图语法将字符串上的形式文法扩充为图上的形式文法,提供一种能够使用精确的数学方法来模拟图变换的机制.提出了几种新的基于一致图语法的方法来表示控制流图、数据流图、控制数据流图、二分图和超图,并说明如何通过图重写来自动生成依赖图并挖掘并行性,从而协助并行编译器和并行语言的设计和实现.     

A comparison of boundary graph grammars and context-free hypergraph grammars

Context-free hypergraph grammars and boundary graph grammars of bounded nonterminal degree have the same power, both for generating sets of graphs and for generating sets of hypergraphs. Arbitrary boundary graph grammars have more graph generating power than context-free hypergraph grammars, but they have the same hypergraph generating power. To obtain these results, several normal forms for boundary graph grammars are given. It is also shown that the class of boundary graph languages is closed under the operation of edge contraction, where the label of the edge indicates whether or not the edge should be contracted.     

Graph Grammars for Querying Graph-like Data

Recently research has deeply investigated the problem of querying semi-structured data and data which can be represented by means of graphs (e.g. object-oriented data, XML data, etc.). Typically queries on graph-like data, called path queries, are expressed by means of regular expressions denoting paths in the graph. The result of a path query is the set of nodes reachable by means of a path expressed by a specified regular expression. In this paper we investigate the problem of extracting a subgraph satisfying a given property from a given graph representing some information. We propose a new form of queries, called graph queries, whose answers are (marked) graphs having a particular structure, extracted from the source graph. We show that a simple form of graph grammars can be profitably used to define graph queries. The result of a graph query, using a grammar G over a database D, is a marked subgraph of D ‘matching’ a graph derived from G. We consider different types of graph grammars which can be used to query graph-like data and consider their expressiveness and complexity.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

软件图语言的形式描述

本文从语言学和形式化角度对软件领域中广泛使用的软件图进行了研究，提出了软件图语言这一概念。本文首先提出了关于软件图语言的一组基本概念，其次研究软件图语言的同态和同构，以构成软件图形式描述的基础；最后讨论了软件图语言的形式表示法，并提出了基于图符网的文法，使图文法更适合于表示软件图语言。本文工作可以作为设计面向软件图语言的软件工具的基础。     

Context-free graph grammars and concatenation of graphs

An operation of concatenation is defined for graphs. This allows strings to be viewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class of string languages, is the class of all graph languages that are interpretations of languages from . For the classes REG and LIN of regular and linear context-free languages, respectively, . is the smallest class of graph languages containing all singletons and closed under union, concatenation and star (of graph languages). equals the class of graph languages generated by linear HR (= Hyperedge Replacement) grammars, and is generated by the corresponding -controlled grammars. Two characterizations are given of the largest class such that . For the class CF of context-free languages, lies properly inbetween and the class of graph languages generated by HR grammars. The concatenation operation on graphs combines nicely with the sum operation on graphs. The class of context-free (or equational) graph languages, with respect to these two operations, is the class of graph languages generated by HR grammars. Received 16 October 1995 / 18 September 1996     

Algorithms for maximum weight induced paths

A family of graphs is a k-bounded-hole family if every graph in the family has no holes with more than k vertices. The problem of finding in a graph a maximum weight induced path has applications in large communication and neural networks when worst case communication time needs to be evaluated; unfortunately this problem is NP-hard even when restricted to bipartite graphs. We show that this problem has polynomial time algorithms for k-bounded-hole families of graphs, for interval-filament graphs and for graphs decomposable by clique cut-sets or by splits into prime subgraphs for which such algorithms exist.     

vCGG:一种基于虚结点的空间图文法形式框架

作为一种二维的形式化方法,图文法为可视化语言提供了直观而规范的描述手段.然而,大多数图文法形式框架在空间语义处理能力方面有所不足,影响了图文法的表达能力及其实际应用范围.针对现存的问题,构建了一种新型空间图文法形式框架vCGG （virtual-node based coordinate graph grammar）.区别于其他空间图文法,vCGG在产生式中通过定义虚结点的概念描述产生式与主图之间的语法结构与空间语义关系,在保留抽象能力的同时,提高了其空间语义配置性能.通过与几种典型空间图文法框架比较,vCGG形式框架在直观性、规范性、表达能力以及分析效率方面均有着较好的表现.     

On the generative capacity of compound string and array grammars

The operation of composition is a device introduced by Abraham [1] to increase the generative capacity of regular matrix grammars. But not all families of grammars have their generative capacity increased by this operation. P?un [5] has proved that composition increases the generative capacity of linear grammars but not of regular, CF, CS or PS grammars. In this note, we show that the generative power of k-linear (k ? 1) grammars is increased by composition. In fact, it is of interest to note that the families of compound linear and compound k-linear languages are equal. Furthermore, the family of compound linear languages is an AFL, properly contained in the family of CFLs. Certain other families of string and array grammars whose generative capacities are increased by the operation of composition are also provided.     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

Generation,recognition and parsing of context-free languages by means of recursive graphs

A device called recursive graph defining context-free languages is described. Previously such a device was used byConway [1] for a compiler design.Conway called it “transition diagram”. Roughly, a recursive graph is a finite set of finite state graphs, which are used in a recursive manner. A recursive graph covers the essential features of both standard devices: It describes the syntactical structure as grammars do, and it represents a method for recognition and parsing as push-down automata do. A notion ofk-determinacy is introduced for recursive graphs and for a restricted kind of them, called simple recursive graphs. Thek-deterministic simple recursive graphs are more general thanLL (k) grammars [5] with respect to parsing-power, but equal with respect to language generation power. The more generalk-deterministic recursive graphs cannot parse the full set ofLR (k)-grammars [4], but they can recognize the full set ofLR (k)-languages. The set of languages recognized by (simple) recursive graphs is the set of context-free languages.     

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.     

Graph grammars with neighbourhood-controlled embedding

A central feature that distinguishes graph grammars (we consider grammars generating sets of node-labelled undirected graphs only) from string grammars is that in the former one has to provide a mechanism by which a daughter graph (the right-hand side of a production) can be embedded in the rest of the mother graph, while in the latter this embedding is provided automatically by the structure that all strings possess (left-to-right orientation). In this paper we consider a possible classification of embedding mechanisms for (node-rewriting) graph grammars. This classification originates from the basic ideas of [9]. On the one hand it allows one to fit a number of existing notions of a graph grammar into a common framework and on the other hand it points out new “natural” possibilities for defining the embedding mechanism in a graph grammar. The relationship between the graph-language generating power of graph grammars using various embedding mechanisms is established.     

A graph isomorphism algorithm for object recognition

We present an algorithm to solve the graph isomorphism problem for the purpose of object recognition. Objects, such as those which exist in a robot workspace, may be represented by labelled graphs (graphs with attributes on their nodes and/or edges). Thereafter, object recognition is achieved by matching pairs of these graphs. Assuming that all objects are sufficiently different so that their corresponding representative graphs are distinct, then given a new graph, the algorthm efficiently finds the isomorphic stored graph (if it exists). The algorithm consists of three phases: preprocessing, link construction, and ambiguity resolution. Results from experiments on a wide variety and sizes of graphs are reported. Results are also reported for experiments on recognising graphs that represent protein molecules. The algorithm works for all types of graphs except for a class of highly ambiguous graphs which includes strongly regular graphs. However, members of this class are detected in polynomial time, which leaves the option of switching to a higher complexity algorithm if desired.     

Multipass precedence analysis

Summary This paper defines a hierarchy of languages which is properly contained in the context sensitive languages and which starts with the context free family. The hierarchy is defined inductively by controlling labeled linear grammars with languages in one family to yield languages in the next larger family. The families of the hierarchy have properties analogous to those of the context free family, in particular, the new mechanism introduced is very suitable for parsing.A language in the n-th family is specified by a sequence of n — 1 labeled linear grammars and a context free grammar. By assuming that the reversals of the first n — 1 grammars and the last labeled linear grammar are precedence grammars, the concepts and parsing algorithm of Wirth and Weber extend to yield a parsing algorithm within the hierarchy. This considerably enhances the usefulness of the construction and allows much of the power of the context sensitive languages to become accessible in measured amounts for potential programming applications.     

Categorical approach to the construction of fuzzy graph grammars

The categorical approach is proposed to the formalization of fuzzy graph grammars obtained as a result of generalization of sequential graph grammars. This approach takes into consideration the basic types of fuzziness that arise in constructing categories of fuzzy objects and describing transformations of fuzzy graphs generated by fuzzy sets. All the problems of undecidability that are well known for Chomsky grammars are proved to hold true for fuzzy graph grammars. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 130–144, July–August 2006.     

Apex graph grammars and attribute grammars

Summary Apex graph grammars are a particular type of directed node-label controlled (DNLC) graph grammars: the embedding edges are established between terminal nodes only. Apex graph grammars, slightly generalized, can generate the sets of dependency graphs of attribute grammars. The other way around, every apex graph language can be obtained from such a dependency graph language by a graph replacement (which is an operation analogous to a string homomorphism).     

Diameter and Treewidth in Minor-Closed Graph Families

It is known that any planar graph with diameter D has treewidth O(D) , and this fact has been used as the basis for several planar graph algorithms. We investigate the extent to which similar relations hold in other graph families. We show that treewidth is bounded by a function of the diameter in a minor-closed family, if and only if some apex graph does not belong to the family. In particular, the O(D) bound above can be extended to bounded-genus graphs. As a consequence, we extend several approximation algorithms and exact subgraph isomorphism algorithms from planar graphs to other graph families.