In order to understand, analyze and modify software, we commonly examine and manipulate its architecture. For example, we may want to examine the architecture at different levels of abstraction. We can view such manipulations as architectural transformations, and more specifically, as graph transformations. We evaluate relational algebra as a way of specifying and automating the architectural transformations. Specifically, we examine Grok, a relational calculator that is part of the PBS toolkit. We show that relational algebra is practical in that we are able to specify many of the transformations commonly occurring during software maintenance and, using a tool like Grok, we are able to manipulate, quite efficiently, large software graphs; this is a "win". However, this approach is not well suited to express some types of transforms involving patterns of edges and nodes; this is a "loss". By means of a set of examples, the paper makes clear when the approach wins and when it loses.

In order to understand and improve software, we commonly examine and manipulate its architecture. For example, we may want to examine the architecture at different levels of abstraction or zoom-in on one portion of the system. We may discover that the extracted architecture has deviated from our mental model of the software and hence we may want to repair it. The paper identifies the commonality between these architectural transformation actions, i.e., by manipulating the architecture in order to understand analyze, and modify the software structure, we are in fact performing graph transformations. We categorize useful architectural transformations and describe them within the framework of graph transformations. By describing them in a unified way, we gain a better understanding of the transformations and thus, can work towards modeling, specifying and automating them.

In order to understand, analyze and possibly modify software, we commonly examine and manipulate its architecture. For example, we may want to examine the architecture at different levels of abstraction or repair the architecture if it has deviated from our mental model of the software. We can view such manipulations as architectural transformations, and more specifically, as graph transformations. In this paper, we use graph rewriting to specify these transformations so that we can work towards automating them. Specifically, we use the PROGRES tool to formulate executable graph-rewriting specifications for various architectural transformations in order to demonstrate the strengths of using graph rewriting. We have applied our executable specifications to small graphs and our results confirm that graph rewriting offers a high-level visual notation that can be used to neatly specify graph modifications, as well as supporting prototype implementations. It also provides a convenient and intuitive framework for exploring various architectural transformations.

In image analysis, recognition of the primitives plays an important role. Subsequent analysis is used to interpret the arrangement of primitives. This subsequent analysis must make allowance for errors or ambiguities in the recognition of primitives. In this paper, we assume that the primitive recognizer produces a set of possible interpretations for each primitive. To reduce this primitive-recognition ambiguity, we use contextual information in the image, and apply constraints from the image domain. This process is variously termed constraint satisfaction, labeling or discrete relaxation. Existing methods for discrete relaxation are limited in that they assume a priori knowledge of the neighborhood model: before relaxation begins, the system is told (or can determine) which sets of primitives are related by constraints. These methods do not apply to image domains in which complex analysis is necessary to determine which primitives are related by constraints. For example, in music notation, we must recognize which notes belong to one measure, before it is possible to apply the constraint that the number of beats in the measure should match the time signature. Such constraints can be handled by our graph-rewriting paradigm for discrete relaxation: here neighborhood-construction is interleaved with constraint-application. In applying this approach to the recognition of simple music notation, we use approximately 180 graph-rewriting rules to express notational constraints and semantic-interpretation rules for music notation. The graph rewriting rules express both binary and higher-order notational constraints. As image-interpretation proceeds, increasingly abstract levels of interpretation are assigned to (groups of) primitives. This allows application of higher-level constraints, which can be formulated only after partial interpretation of the image.

Graph grammars provide a useful formalism for describing structural manipulations of multidimensional data. The authors review briefly theoretical aspects of graph grammars, particularly of the embedding problem, and then summarize graph-grammar applications. Currently graph grammars are used most successfully in application areas other than pattern recognition. Widespread application of graph grammars to picture processing tasks will require research into problems of large-scale grammars, readability of grammars, and grammatical processing of uncertain data.>