On the Automated Design
of Technical Systems
From the
Department of Mathematics and Computer Science
of the University of Paderborn, Germany
The Submitted Dissertation of
André Schulz
In Order to Obtain the Academic Degree of
Dr.rer.nat.
Advisor: Prof. Dr. Hans Kleine Büning
Reading Committee: Prof. Dr. Gregor Engels
Date of Oral Examination: November 19th, 2001
Acknowledgments
This thesis is a result of my work in the Knowledge-based Systems
Group, Department of Methematics and Computer Science, University
of Paderborn.
I wish to thank my thesis advisor, Professor Dr. Kleine Büning, for
his support of my work, as well as Professor Dr. Engels for evaluating
this thesis.
I also wish to thank all my colleagues for the valuable discussions,
hints and corrections throughout my work on this thesis. I owe special
thanks to Dr. Benno Stein for numerous discussions and for his rigor-
ous guidance from which my work benefitted a great deal, and to Dr.
Theo Lettmann for his technical and moral support.
Finally, I wish to thank my family and friends for the encourage-
ment and support.
André Schulz
4
Contents
1 Introduction 1
1.1 Thesis Structure ........................ 4
1.2 Design Support ........................ 5
1.3 Model Simplification ..................... 7
2 A Design Task 13
2.1 Caramel Syrup Example—Structure ............ 16
2.2 Caramel Syrup Example—Behavior ............ 18
3 Graph Grammar Model for Design 21
3.1 Design Tasks and Graph Transformation Rules ...... 21
3.2 Context-free Design Graph Grammar ........... 28
3.3 Context-sensitive Design Graph Grammar ......... 32
3.4 On the Semantics of Labels .................. 35
3.4.1 Terminal and Nonterminal Labels ......... 35
3.4.2 Variable Labels .................... 36
3.4.3 Ambiguities ...................... 37
4 Analyzing Systems 39
4.1 Structure Analysis by Graph Grammars .......... 40
i
Contents
4.2 Caramel Syrup Example ................... 43
4.3 Behavior Analysis by Simulation .............. 45
4.3.1 Classical Simulation ................. 47
4.3.2 Qualitative Simulation ................ 48
4.3.3 Complexity of Design Evaluation .......... 49
5 Synthesizing Systems 51
5.1 Structure Synthesis by Graph Grammars ......... 52
5.2 Caramel Syrup Example Reviewed ............. 53
5.3 Graph Topology Restrictions ................ 55
5.4 Search Techniques ....................... 56
5.4.1 Label Ordering .................... 57
5.4.2 Reinforcement Learning ............... 59
5.4.3 Model Compilation .................. 60
6 Design Language 63
6.1 Requirements ......................... 64
6.1.1 Modification Types .................. 64
6.1.2 Modification Location ................ 65
6.2 Semantics of Graphical Representation ........... 66
6.3 Caramel Syrup Example Reviewed Again ......... 68
7 Classes, Complexity and Design Evaluation 73
7.1 Classical and Design Graph Grammars .......... 74
7.1.1 The Connecting Approach .............. 75
7.1.2 The Gluing Approach ................ 78
ii
Contents
7.1.3 Hybrid Approaches ................. 79
7.1.4 Design Graph Grammars .............. 82
7.2 Relationship to PGRS ..................... 84
7.3 The Problem of Matching .................. 86
7.3.1 Context and Its Consequences ........... 87
7.3.2 The Subgraph Matching Problem .......... 88
7.3.3 Context within Backward Execution ........ 89
7.4 Foundations of Derivations and Membership ....... 90
7.4.1 Basic Properties .................... 90
7.4.2 Special Restrictions .................. 92
7.5 Membership and Derivation in Design ........... 96
7.5.1 The Membership Problem .............. 97
7.5.2 Solving the Membership Problem .........100
7.5.3 Shortest Derivation ..................103
7.5.4 Distance between Graphs ..............107
8 Summary 111
Bibliography 112
A Applications in Design 121
A.1 Structural Synthesis: Chemical Plants ...........122
A.2 Structural Simplification: Hydraulic Plants ........131
A.3 Structural Synthesis: Hydraulic Plants ...........137
A.4 Model Reformulation: Wave Digital Structures ......140
A.5 Model Reformulation: Parallel-Series Graphs .......143
iii
1 Introduction
The design of a technical system is a process usually dealing with a
non-trivial number of components and relations; it remains a major
challenge for present-day designers. Besides, the design process usu-
ally consists of a set of different tasks, such as analysis and optimiza-
tion: design does not mean configuration alone, as is the general per-
ception.
When tackling a design job, it is useful to look at different models
of a system from the viewpoints of structure and behavior, which, de-
pending on the modeling paradigm, are either loosely or tightly con-
nected to each other [Stein,2001]. Modern design tools focus mainly
on the formulation and processing of behavior models. Support for
behavioral aspects of the design process is indeed essential due to the
time-consuming nature of behavior-related tasks; tasks pertaining to
structural models, which require a great deal of creativity, are usually
efficiently solved by human experts. Figure 1.1 illustrates this idea.
Structure
Model Behavior
Model
Task Expected
Behavior
Resulting
Behavior
Synthesis Parameterization
Analysis
Evaluation
Manual Processing Automatic Processing
Figure 1.1: The design process according to [Gero,1990]andmodified
by Stein [Stein,1995], and the tasks that are traditionally solved man-
ually and automatically
1
1Introduction
Although support for the synthesis of structure models may seem
questionable, it is nonetheless an important step of the design process.
This thesis focuses on the structural aspects of the design tasks and
aims at providing a foundation for a holistic support of the design pro-
cess.
The design process is—depending on the modeling paradigm and
granularity—very complex and at this level even simpler tasks re-
main toilsome. Thus, we resort to Functional Abstraction, a paradigm
within the model construction theory developed by Stein in [Stein,
2001], in order to make the task tractable. Stein informally introduces
the paradigm of functional abstraction in the following way:
“At first, we construct a poor solution of a design problem,
which then must be repaired.”
In particular, functional abstraction comprises four steps: By means
of model simplification, the original task is abstracted. At this simplified
level, a coarse design can be efficiently generated and, subsequently,
enriched with behavior by adding behavior model parts to the struc-
ture model. This enriched structure model represents a possibly faulty
design; repair mechanisms are required to produce an acceptable de-
sign. Figure 1.2 illustrates the concept of functional abstraction.
Simplification
Behavior
Level
Function
Level
Original
Task
Abstracted
Task Structure
Model
Behavior Model
(coarse) Solution
Figure 1.2: Efficient solution of a design task by means of functional
abstraction [Stein,2001].
2
The main contribution of this thesis is the automation of the step
“abstracted task →structure model”. Given a description of the de-
mands implied by the abstracted task, e. g., in the form of inputs and
outputs, and a set of parameterized system building blocks, both the
selection and the connection of the necessary building blocks shall be
derived. Moreover, the analysis and improvement of structure and be-
havior of a given design is also addressed. In order to achieve these
goals, state-of-the-art search techniques and knowledge acquisition
methods are adapted and applied.
The essence of our approach is as follows. A technical system is
viewed as a graph, the nodes of the graph describe system building
blocks, the edges of the graph specify the connections between build-
ing blocks and enable the exchange of information and energy. Modi-
fications of a technical system are defined as node-insertion and node-
deletion operations on the graph. We use graph grammars as a proper
means to precisely specify such modifications, say, to encode an engi-
neer’s design knowledge on structure. In order to do this effectively, a
new graph grammar class—the design graph grammar—was devised
to allow for an efficient processing within technical domains.
For illustrative purposes we will resort to the domain of chem-
ical engineering, which is the main area of application of the DFG
project from which this thesis resulted. Note that in this domain
computer-based design support is provided in the form of dedicated
configuration systems for particular devices such as mixers and ag-
itators [Brinkop and Laudwein,1993,Knoch and Bottlinger,1993]or
special heat transfer devices [Götte,1995,Götte and Schmidt-Traub,
1996]. Moreover, there are tools concentrating around simulation, and
yet other design tools were developed as tailored CAD programs
[Räumschüssel et al.,1993,Marquardt,1992,Stephanopoulos et al.,
1990,Piela et al.,1991,Pantelides,1988].
In order to validate our approach, a design tool implementing the
described methodology has been prototypically developed. This tool,
named DIMod (for Domain Independent Modeler), can generate struc-
ture models complying with the underlying design knowledge based
on the abstracted task specification. The generated structure model is
3
1Introduction
enriched with behavior model parts and sourced out to a simulator;
the simulation results have to be evaluated in order to determine the
quality of the solution—this last step, however, has not been integrated
yet into DIMod.
1.1 Thesis Structure
This thesis is organized as follows.
Section 1.2 presents a short survey on the state of the art of modern
systems supporting design tasks. Special attention is given to tools for
the domain of chemical engineering.
Section 1.3 deals with model simplification, a requirement for func-
tional abstraction, and addresses the major simplifications introduced
as well as some issues related to the modeling granularity.
Chapter 2gives a description of chemical design tasks, which is
illustrated by means of a realistic example.
Chapter 3examines the requirements imposed by design tasks and
introduces the concept of design graph grammars.
Chapter 4applies the design graph grammar approach to structure
analysis and briefly discusses the simulation of the underlying model.
Chapter 5applies the design graph grammar approach to structure
synthesis. Furthermore, search techniques for an efficient generation
process are investigated.
Chapter 6sheds some light on different design topics: design repair
and optimization.
Chapter 7supplies a theoretical foundation related to the area of
graph grammars. The relationship between design graph grammars
and the classical approaches is addressed in detail, and special atten-
tion is given to design-related issues.
The appendix contains practical examples of design graph gram-
mars used within different domains.
4
1.2 Design Support
1.2 Design Support in Chemical Engineering
According to Marquardt [Marquardt,1992], modern process model-
ingtoolscanberoughlyclassifiedinto two types: block-oriented (also
called modular) and equation-oriented approaches.
Block-oriented approaches correspond to modeling on the flow-
sheet level. The user or engineer works with standardized building
blocks which model the behavior of a process unit-operation or part
of it. Chemical plants are designed by choosing building blocks from
a library of standard building blocks and by connecting them appro-
priately. These approaches require that an expert create the model li-
braries and allow the user to use them at the abstract level described
above. The manipulation of these building blocks is usually supplied
by modeling languages or visual editors.
Equation-oriented approaches allow for the implementation of
models and libraries built thereof by means of declarative modeling
languages or template routines that can be embedded directly into
some procedural programming language, such as Fortran. These ap-
proaches do not provide any modeling tools for experts or users,
thereby requiring profound knowledge of the domain.
Since the early 1980’s, various projects whose primary goals were
to provide support for process modeling have been engaged. Only a
few of these projects were successful, and the development of some
systems has been suspended altogether. The following table, based
mainly on [Marquardt,1996], lists some of the projects together with
their features1:
1Empty entries mean that no information about this specific feature is available and
should not be interpreted as lack thereof.
5
1Introduction
Tool/ Visual Modeling Uses AI Process
Language Class modeler language simul.
Ascend block general X
Diva/
Veda equation process X X
Dylan general X
Dymola block Xgeneral X
gProms/
SpeedUp equation general X
HPT process X
Modass process X
Design-Kit/
Model.la process X
Modeller process
Modex process X
ModKit Xprocess X
OmSim/
Omola block Xgeneral X
Profit process X
DIMod block Xgeneral X X
The alleged features of some systems could not be checked by the
author due to availability issues. Though some tools may share the
same properties, they often do so to varying degrees. The use of ar-
tificial intelligence, for instance, is often limited to the availability of
assistants or wizards, or, in a few cases, to an “intelligent” preprocess-
ing of the equation systems.
The approaches presented in this thesis were implemented to a cer-
tain extent in DIMod, a process modeling tool prototype developed at
the University of Paderborn; they are described in detail in the chap-
ters 4,5and 6. The main concern in DIMod is the support for structure-
related tasks; process simulation support is restricted to qualitative
simulation or sourced out to third-party simulation tools2.
2At the present development stage only Ascend is supported.
6
1.3 Model Simplification
Although DIMod possesses many features common to modern
tools, it outstands in its ability to automatically synthesize and ana-
lyze structure models.
1.3 Model Simplification
An automation of the design steps at the original model level would
be very expensive—present systems limit automation to human-un-
friendly tasks like simulation, and the effort involved there is high
enough. However, our goal is to provide support throughout the de-
sign procedure, and at this level fine granular processing remains in-
surmountable with present-day technology.
Another pressing reason for a modeling depth shift is the targeted
design support type, namely the automation of structure related tasks.
Within this scope information pertaining to the physical properties of
a system does not play a major role.
Instead of deriving a concrete solution at the modeling level im-
posed by the supplied demands, the original task is simplified. On
this abstract level, a solution can be efficiently calculated and trans-
ferred back to the physical level, although some adjustments may be
necessary at this point (see chapter 6).
The following model simplification steps—named according to
[Frantz,1995]—lead to a more tractable design problem:
•Model boundary simplification. Assumptions pertaining to the ex-
ternal features of the model—input variable space, global restric-
tions etc.—are made:
–Simple task assumption. It is general practice to combine dif-
ferent chemical processes that share some partial chains in
order to save costs. Such a combination corresponds to the
solution of different tasks simultaneously. However, this
procedure belongs to optimization; therefore, overlapping
plant structures are segregated and dealt with separately,
7
1Introduction
i. e., we solve each task individually. The following figure
illustrates this concept.
–Model context. The way models, or parts of models, are em-
bedded into a context is clearly defined. Pumps, for exam-
ple, have a strict structural relationship; they have one input
and one output, i. e., the degree is fixed, and the predecessor
of a pump must be another device.
–Limited input space. Firstly, we concentrate on tasks of the
food processing branch of the chemical engineering do-
main. This restriction results in further simplifications: The
chemical plants to be designed do not exceed a certain mag-
nitude, as well as the range of some variables, such as tem-
perature, which is limited to “small” values, say, below
200°C.
Furthermore, the focus is laid on liquid mixtures. This
means that at least one input has to be a fluid.
Another restriction is the number of relevant substance
properties. During design generation, decisions are taken
based on the abstract values of a small set of substance
properties, such as temperature, viscosity, density, mass and
state. Properties such as heat capacity, heat conductivity or
critical temperature and pressure are neglected at this point.
8
1.3 Model Simplification
–Approximation. Instead of using different functions and for-
mulas that apply under different conditions, only one func-
tion or formula covering the widest range of restrictions is
used in each case. For example, there are over 50 differ-
ent formulas to calculate the viscosity of a mixture, most
of which are very specialized versions and only applica-
ble under very rare circumstances—the formula ln(
η
)=
∑i
ϕ
i·ln(
η
i), however, is very often applicable and deliv-
ers a good approximation, even in the complicated cases.
•Behavioral simplification. Now the focus is shifted to aspects
within the model, where the behavior of components is simpli-
fied:
–Causal decomposition. To prevent components from exerting
influence on themselves, feedback loops are ruled out. This
simplification step makes structural manipulation and be-
havioral analysis easier.
The situation depicted below shows a cycle within a chemi-
cal plant. The purpose of the backward edge is to transport
evaporated substance back into the mixer; this gaseous sub-
stance condenses on the way.
–Numeric representation. Although the use of crisp values
leads to exact results, fuzzy sets are used to represent essen-
tial value ranges. This simplification diminishes the combi-
natorial impact on our graph grammar approach, since sub-
stance properties are coded into edge labels and the use of
crisp values would lead to an excessive number of rules.
The following figure shows the fuzzy representation of the
substance property “viscosity”:
9
1Introduction
500 5000
0.5
1.0
01
low medium high
mPas
–State aggregation. In general, the material being processed
within a device is not in one state, but actually in various
different ones. For instance, inside a heat transfer device a
fluid may be, depending on the reading point, cold, warm,
in liquid form or gaseous. This behavior is simplified by as-
suming that, inside any device, a material will be in one sin-
gle state.
–Temporal aggregation. Time is neglected, making any state-
ments about continuous changes to material properties no
longer possible; changes to material properties are con-
nected to entry and exit points within the plant structure.
–Entity aggregation by function. Different device entities are
represented by one device performing a function common
to all devices. For example, all different mixer types could
be described by one special mixer, as shown below.
–Entity aggregation by structure. Devices usually consist of dif-
ferent parts that can be configured separately. For instance,
a plate heat transfer device is composed of a vessel and a
variable number of plates. The arrangement of the plates
within the vessel is a configuration task.
10
1.3 Model Simplification
The following figure sketches the composition of a plate
heat transfer device and of an anchor mixer.
+
+ +
–Function aggregation. In contrast to entity aggregation by
function, where devices are represented by a special device,
we aggregate here functions. For instance, mixers are capa-
ble of performing different functions, such as homogeniza-
tion, emulsification, aeration, suspension etc.
•Derived relationships. Some fields of chemical engineering still re-
main unveiled and are dealt with as black boxes. In such cases
one has to resort to look-up tables and interpolation, as far as
sufficient information is available. For example, the output of
a mixer, measured in terms of the Reynolds and Newton num-
bers, has to be determined experimentally, and this data is usu-
ally only available as tables.
Remarks.
The model simplification steps listed above can be classified
into two different types: Steps pertaining to the model structure and
steps belonging to the model behavior. Note that steps may be con-
nected to both structure and behavior.
The steps that simplify the model structure—simple task assump-
tion, model context, limited input space, causal decomposition, nu-
meric representation, entity aggregation by function—yield a model
that is fitting to be processed with graph grammars. These steps re-
strict the graph structure and specify the types and granularity of node
and edge labels.
The steps belonging to the model behavior—limited input space,
approximation, causal decomposition, numeric representation, state
and temporal aggregation, entity aggregation by structure, function
aggregation, derived relationships—result in a model suitable for
qualitative simulation, as described in chapter 4.
11
1Introduction
The model simplification steps performed here relate to the domain
of chemical engineering. For other domains not necessarily the same
steps will be appropriate; the modeler has to determine which model
simplification steps are fitting individually.
12
2 A Design Task from the Domain of
Chemical Engineering
The approach presented in this thesis may be suited to tackle various
kinds of design problems in different domains. However, we concen-
trate on a particular part of chemical engineering: The design of plants
for the food processing industry.
A chemical plant can be viewed as a graph, where the nodes rep-
resent the devices, or unit-operations, and the edges correspond to
the pipes responsible for the material flow. Typical unit-operations
are mixing (homogenization, emulsification, suspension, aeration etc.),
heat transfer, and flow transport. Modifications of a chemical process
include the insertion of devices, rearrangement of chains, removal or
substitution of redundant devices etc. At the abstract level these mod-
ifications match the graph operations mentioned earlier.
The task of designing a chemical plant is defined, as in many other
fields, by the given input and the desired output. The goal is to mix
or transform various input substances in such a way that the result-
ing product meets the imposed requirements—in order to achieve this
goal, a chemical plant, consisting of properly configured devices, has
to be devised. Figure 2.1 illustrates the solution process followed in
general practice.
The steps depicted in Figure 2.1 can be described in more detail as
follows:
1. Preliminary examination. This step includes any preparatory mea-
sures that must be taken prior to beginning with the design pro-
cess. This includes examining the task specification, i.e., the input
13
2 A Design Task
Solution
Task Preliminary examination
Choice of unit-operations
Structure definition
Configuration of components
Optimization
Figure 2.1: Steps in the design process of a chemical plant.
substances and the desired output, from which possibly implicit
information can be extracted. For instance, the input substances
may differ in a certain essential property like “solubility in wa-
ter”, and, if there are more than two input substances, it might
be necessary to process the ones belonging to the same solubility
type before dealing with all input substances together. This can
be done by grouping or clustering the substances according to
prespecified properties.
2. Choice of unit-operations. After examining the substances involved
in the desired chemical process, abstract building blocks, so-
called unit-operations, are chosen in compliance with certain
rules. For example, if the output mixture should have a temper-
ature that is substantially different from the temperature of the
input substances, then the unit-operation heat transfer is needed.
Moreover, using the example of the last step, if at least two sub-
stances have different solubility properties, then the unit-opera-
tion emulgation is necessary. Similarly, any other conclusions con-
cerning the choice of unit-operations are drawn in a rule-based
fashion.
In practice, engineers choose concrete devices at this stage—the
use of abstract building blocks is done implicitly.
14
3. Structure definition. The previous step produces a set of unit-op-
erations devoid of any structure, i.e., the unit-operations are still
“unconnected”. To find an apt topology, different circuits are
tried until one that meets the requirements is found. This well-
known propose-and-revise behavior has been also applied to the
field of chemical engineering [Brinkop and Laudwein,1993].
Typically, the initially devised topology represents a good solu-
tion. However, a first calculation of the resulting mixture and
its properties may show that certain constraints, such as max-
imum mixing time, cannot be met by the proposed topology.
Therefore, the engineer may have to adapt his initial solution by
adding or removing certain devices, or the topology itself has to
be changed. This procedure is reiterated until all requirements
are met.
4. Configuration of devices. The chosen devices, still represented by
unit-operations, are instantiated. Beginning with the first unit-
operation in the process chain, concrete devices are chosen from
a database. Since different devices of the same class often pro-
duce outputs with slightly different properties, these changes
must be propagated throughout the chain, thus influencing the
choice of later devices.
Alternatively, this step may also be performed before the struc-
ture is defined (but no propagation takes place at this point).
5. Optimization. The plant’s functionality is tested whether it meets
the imposed requirements. If the designed plant fails to fulfill
any of these requirements, some changes have to be applied ei-
ther to the structure or to the set of chosen devices.
Even if the plant represents a solution to the problem, the engi-
neer might still want to refine it to reduce energy consumption
or to decrease mixing time. These optimizations or modifications
also require some changes to the plant, making the return to a
previous step obligatory.
15
2 A Design Task
2.1 Caramel Syrup Example—Structure
We now present a concrete example for the design process described
in section 2. Here the emphasis is laid on the structure of the design;
section 2.2 will address the behavior of the design.
The following task specification excerpt shall help illustrate the
usual design procedure performed by an engineer.
Name State Mass Temp. Viscosity
sugar solid 47.62% 20°C –
water liquid 15.75% 20°C 0.0010012 Pas
starch syrup liquid 36.63% 20°C 0.2-1.6 Pas
caramel syrup liquid 100.00% 110°C ?
The goal is to produce caramel syrup, which is necessary for the
production of caramel bonbons, using water, starch syrup and sugar.
The following table containing viscosity values of sugar solution,
a possible intermediate product, is also available, although it does not
belong to the task specification per se:
Temperature Viscosity (71% solution)
0°C 5000 Pas
10°C 1000 Pas
20°C 500 Pas
30°C 250 Pas
40°C 130 Pas
50°C 80 Pas
60°C 50 Pas
70°C 30 Pas
80°C 20 Pas
Based on this task specification, the following steps pertaining to
the structure are performed in compliance with the general procedure
depicted in section 2:
16
2.1 Caramel Syrup Example—Structure
1. Preliminary examination. The first observation made by the engi-
neer is that one of the substances, sugar, is a solid and must be
dissolved within one of the other input liquids. Since water has
a lower viscosity than starch syrup, it will be better to mix sugar
and water first and then add the starch syrup to the solution.
Depending on the mass ratios the water may have to be heated
beforehand to increase solubility.
2. Choice of unit-operations. The comparison of the mass ratios of
sugar and water leads to the conclusion that heating is necessary;
thus, a heat transfer unit-operation is needed to heat the water.
The heated water and the sugar are then mixed—for this purpose
a mixing unit-operation for lower viscous substances is appro-
priate. To avoid recrystallization, the starch syrup should also be
heated, thereby making another heat transfer unit-operation nec-
essary. Finally, the heated sugar solution and the heated starch
syrup are mixed. In order to reach the required temperature of
110°C, another heat transfer unit-operation will be needed. Fur-
thermore, pump unit-operations are required to transport the
substances between devices.
3. Structure definition. The choice of unit-operations, although hav-
ing no direct impact on the structure, allows for certain conclu-
sions pertaining to the ordering of the unit-operations. In this
case this ordering is relatively evident; Figure 2.2 shows the cho-
sen topology.
Starch
syrup
Water
Sugar
Caramel
syrup
Figure 2.2: The first design of the example process.
17
2 A Design Task
2.2 Caramel Syrup Example—Behavior
The example presented in the previous section shows how an abstract
design can be generated, using a simplified task description. The re-
sult of the generation process is a feasible structure complying with the
simplified demands. This, however, does not represent a complete de-
sign, since all devices remain abstract. Thus, this abstract model must
be enhanced with concrete device data—static and dynamic parame-
ters.
The following steps determine the behavior of the design and make
some corrections, if applicable:
4. Configuration of devices. Based on the mass, the volume, and the
other properties of the involved substances, matching devices
are chosen from databases or data sheets. For the sake of simplic-
ity we will refrain from a detailed description here and refer to
Figure 2.3, where the abstract design with additional data from
the underlying model is shown.
5. Optimization. The computed properties of the plant design usu-
ally represent feasible values, but improvement may still be pos-
sible. With this goal in mind, the parameterization process is re-
peated and parameters adjusted accordingly. In our case the last
heat transfer unit-operation of the process chain represents an
overkill—the last mixing unit-operation is then slightly changed
so that only devices with a built-in heat transfer unit are consid-
ered. This change shortens the process chain, thereby reducing
costs and mixing time. The final design is depicted by Figure 2.3.
Alternatively, another design with fewer devices is conceivable.
For instance, water and starch syrup can be mixed first, and the re-
sulting solution used to dissolve sugar. This structure choice would
require one heat transfer unit-operation less than the proposed design
because both water and the starch syrup have to be heated to the same
temperature, which is best done if both substances are mixed together
beforehand. However, this alternative would cause a longer mixing
18
2.2 Caramel Syrup Example—Behavior
Starch
syrup
Water
Sugar
Caramel
syrup
[0-50C]
[0-50C]
45l
40l
15kg
[0-0.5 m3/h]
[0-0.5 m3/h]
[0-0.5 m3/h]
20C
20C
70C
70C
70C, ≤0.2Pas
70C, ≤0.001Pas
Propeller
75% Solution
≈ 60-70C
≈ 30Pas
100l
≤ 110C
≈ 4Pas
Propeller
Range: [0-50C]
≤ 110C
≈ 4Pas
Figure 2.3: Design showing part of the underlying model.
time, since the sugar must be dissolved in a more viscous solution
(compared to pure water). Figure 2.4 shows this alternative solution.
Starch
syrup
Water
Sugar
Caramel
syrup
Figure 2.4: Alternative design of the example process.
19
2 A Design Task
20
3 Graph Grammar Model for Design
Each of the steps depicted in Figure 2.1 can be automated in an isolated
fashion. However, a separate processing may lead to loss of informa-
tion, since the choice of a unit-operation often affects the structure and
vice versa. For example, the choice of a certain mixer might influence
the decision whether a heat transfer device is necessary or not, thereby
possibly causing a change to the topology. Likewise, a certain ordering
of the devices within the plant structure can make one of them super-
fluous.
Due to the intertwined nature of these steps, it is strongly desirable
to combine the choice of unit-operations and the structure definition to
make use of all information available. One way of tackling both tasks
simultaneously is to use a graph grammar to generate feasible designs
in a controlled manner, thus allowing for an incremental execution of
the mentioned steps. The graph grammar will not only be used for con-
trolled generation, but also for analysis tasks, optimization and repair
tasks, and also for dynamic visualization purposes.
In the following we analyze the requirements imposed by the var-
ious design aspects and introduce suitable graph grammar models to
fulfill them. Finally, special issues concerning the semantics of design
graph grammars are addressed.
3.1 Design Tasks and Graph Transformation Rules
A technical system can be described by a labeled graph. The nodes of
the graph designate the system’s items, the graph’s edges define rela-
tions between the items, labels specify the types of nodes and edges.
21
3 Graph Grammar Model for Design
The following definition introduces this concept formally.
Definition 1 (Labeled Graph)
A labeled graph is a tuple G =VG,EG,
σ
Gwhere VGis the set of nodes,
EG⊆VG×VGis the set of directed edges, and
σ
Gis the label function,
σ
G:VG∪EG→Σ,whereΣis a set of symbols, called the label alphabet.
Notation: (v1,v2,l)represents a directed edge with tail v1,headv
2and label
l. {v1,v2,l}denotes an undirected edge with label l, which can be viewed
as two directed edges, (v1,v2,l)and (v2,v1,l). Edges without labels will be
written as (v1,v2)or {v1,v2}.
The design of a system encompasses a variety of different aspects
or tasks and not only the traditional construction process with which
it is usually associated. For each of these tasks different operations of
varying complexity are required:
•Insertion and deletion of single items in a system
•Change of specific item and connection types
•Manipulation of sets of items, e. g., for repair or optimization
The operations delineated above can be viewed as transformations
on graphs; they are of the form target →replacement. A precise specifi-
cation of such “graph transformation rules” can be given with graph
grammars. A central concept in this connection is bound up with the
notions of matching and context, which, in turn, build up on the con-
cept of isomorphism (see, for example, [Jungnickel,1999]). Complexity
issues are addressed in chapter 7.
Definition 2 (Isomorphism, Isomorphism with labels)
Let G =VG,EGand H =VH,EHbe two graphs. An isomorphism
is a bijective mapping
ϕ
:VG→VHfor which holds: {a,b}∈EG⇔
{
ϕ
(a),
ϕ
(b)}∈EH, for any a,b∈VG. If such a mapping exists, G and H
are called isomorphic.
22
3.1 Design Tasks and Graph Transformation Rules
G and H are called isomorphic with labels, if G and H are labeled graphs
with labeling functions
σ
Gand
σ
H, and the following additional condition
holds:
σ
G(a)=
σ
H(
ϕ
(a)) for each a ∈VG,and
σ
G(e)=
σ
H(
ϕ
(e)) for each
e∈EG,where
ϕ
(e)={
ϕ
(a),
ϕ
(b)}if e ={a,b}.
Figure 3.1 shows an example of isomorphic and non-isomorphic
graphs.
a
b
c
d
e
ab
cd
e
a
b
c
d
e
GH1H2
Figure 3.1: A graph G,agraphH1that is isomorphic to G,andagraph
H2that is not isomorphic to G.
Definition 3 (Matching, Context)
Given are a labeled graph G =V,E,
σ
and another labeled graph, C.
Each subgraph VC,EC,
σ
Cin G, which is isomorphic to C, is called a match-
ing of C in G. If C consists of a single node only, a matching of C in G is called
node-based, otherwise it is called graph-based.
Moreover, let T be a subgraph of C, and let VT,ET,
σ
Tdenote a match-
ing of T in G. A matching of C in G can stand in one or more of the following
relations to VT,ET,
σ
T:
1. VT⊂VC,VT=∅. Then the graph VC,EC,
σ
Cis called a context of
TinG.
2. VC,EC,
σ
C=VT,ET,
σ
T. Then T is called context-free.
A matching of a graph T in G is denoted by
T. In general, we will not
differentiate between a graph T and its isomorphic copy.
23
3 Graph Grammar Model for Design
a) b) c)
ab
cd
b
c
G
a
bc
d
T
C
ab
cd
b
c
Tab
cd
b
c
Tab
cd
b
c
T
Figure 3.2: Above, a context graph Cincluding a target graph T,and
ahostgraphG.Below:a)strictdegreematchingofTin G;
b) matching of Tin G; and c) matching of Cin G,butno
context of T.
Figure 3.2 illustrates the notions of matching and context.
Remarks.
Amatching
Tof a graph Twithin another graph Grepre-
sents a subgraph of G, which means that potentially every node of
T
may be connected to the remainder of Gby arbitrarily many edges.
This matching concept may be sufficient for most purposes, but the
domain of technical systems requires more flexibility. Thus, the term
“matching” is refined to allow the matching of nodes with a precise
number of edges. This type of matching is called strict degree matching;
in practice, the use of this type of matching will be indicated by an
asterisk appended to a node instance, as in T={1∗,2},{(1, 2)}.
Existing graph grammar approaches are powerful, but lack within
two respects. Firstly, the notion of context is not used in a clear and
consistent manner, which is also observed in [Rozenberg,1997], page
97. Secondly, graph grammars have not been applied seriously in or-
der to solve synthesis and analysis problems in the area of techni-
cal systems—graph grammar solutions focus mainly on meta prob-
24
3.1 Design Tasks and Graph Transformation Rules
lems [Rozenberg,1997,Ehrig et al.,1999a,b,van Eekelen et al.,1998,
Kaul,1986,1987,Korff,1991,Lichtblau,1991,Rekers and Schürr,1995,
Schürr et al.,1995,Schürr,1997a].
The systematics of design graph grammars introduced here ad-
dresses these shortcomings. Figure 3.3 relates classical graph grammar
terminology to typical design tasks; the following list presents exam-
ples for the differently powerful rule types. A precise analysis of the re-
lationship between classical graph grammar families and design graph
grammars can be found in chapter 7.
Node-based Graph-based
with
context
context-
free
NLC NCE
Insertion,
deletion
(synthesis)
Manipulation
of types
(synthesis,
analysis)
Typed structural
manipulation
(repair, optimization)
Structural
manipulation
(model trans-
formation)
NCE
with
context
context-
free
NCE without
edge labels
Target
Design
Tasks
Classical
Graph
Grammars
Figure 3.3: Graph grammar hierachy for the various design tasks. The
abbreviations NLC and NCE denote classical graph gram-
mar families.
•Node →node: Context-free transformation based on node la-
bels. Graph grammars with rules of this type are called node label
controlled graph grammars (NLC grammars). The following fig-
ure illustrates a type modification of a mixing unit, which can be
realized by this class of rules.
25
3 Graph Grammar Model for Design
•Node →graph: Context-free transformation based on node la-
bels (NLC grammars). The following figure shows the replace-
ment of an ideal voltage source by a resistive voltage source (syn-
thesis without context).
e e
++
•Node with context →node: Node-based transformation based
on node labels and edge labels. Graph grammars with rules of
this type are called neighborhood controlled embedding graph gram-
mars (NCE grammars). The clustering of graphs (analysis and
synthesis with context) is an example for this type of transfor-
mation and is depicted in the following figure.
AB
C
•Node with context →graph: Node-based transformation based
on node labels and edge labels (NCE grammars). The follow-
ing figure shows the replacement of an unknown unit by insert-
ing heat transfer and pump units to fulfill the temperature con-
straints (synthesis with context):
Tlow Thigh TlowThigh
?
The following figure illustrates the replacement of an unknown
unit by inserting a heat transfer unit, a pump unit and a mixing
unit (synthesis with context):
26
3.1 Design Tasks and Graph Transformation Rules
Tlow Thigh Thigh
Thigh Thigh
Tlow
?
•Graph →graph: Context-free transformation based on graphs
without edge labels (NCE grammars without edge labels). The
replacement of two resistors in series by one resistor, an example
for structural manipulation, is depicted below.
Another example for transformation of this type is given by the
conversion of a structure description tree into a parallel-series
graph (model transformation):
S
P
S
∆ ∆ ∆ ∆ ∆
∆∆
∆
∆
∆
•Graph with context →graph: Context-sensitive transformation
based on graphs with edge labels (NCE grammars). The follow-
ing figure shows the insertion of a bypass throttle (repair, opti-
mization), which represents such a transformation.
27
3 Graph Grammar Model for Design
3.2 Context-free Design Graph Grammar
What happens during a graph transformation is that a node, t—or a
subgraph, T—in the original graph Gis replaced by a graph R.Put
another way, Ris embedded into G.
In the following we will provide a formal basis for the illustrated
graph transformations.
Definition 4 (Host Graph, Context Graph, Target Graph, Replacement
Graph, Cut Node)
Within the graph transformation context a graph can play one of the fol-
lowing roles:
•Host graph G. A host graph represents the structure on which the
graph transformations are to be performed.
•Context graph C. A context graph represents a matching to be found
in a host graph G. The graph C is part of the left-hand side of graph
transformation rules.
•Target graph T. A target graph represents a graph whose matching in
a host graph G is to be replaced. If T is a subgraph of a context graph C,
then the occurrence of T within the matching of C in G is to be replaced.
The graph T is part of the left-hand side of graph transformation rules.
In case T consists of a single node, it is called target node and denoted
by t.
•Replacement graph R. A replacement graph represents a graph of
which an isomorphic copy is used to replace a matching of the target
graph T in the host graph. The graph R is part of the right-hand side of
graph transformation rules.
•The nodes of the host graph that are connected to the matching of T are
called cut nodes.
Informally, a graph grammar is a collection of graph transforma-
tion rules, each of which is equipped with a set of embedding instruc-
28
3.2 Context-free Design Graph Grammar
tions. The following definition provides the necessary syntax and se-
mantics.
Definition 5 (Context-free Design Graph Grammar)
A context-free design graph grammar is a tuple G=Σ,P,swith
•Σis the label alphabet used for nodes and edges1,
•P is the finite set of graph transformation rules,
•and s is the initial symbol.
The productions of the set P are graph transformation rules of the form
T→R,Iand with the following semantics: Firstly, a matching of the
target graph T is searched within the host graph G. Secondly, this occurrence
of T along with all incident edges is deleted. Thirdly, an isomorphic copy of
R is connected to the host graph according to the semantics of the embedding
instructions.
•T=VT,ET,
σ
Tis the target graph to be replaced,
•R=VR,ER,
σ
Ris the possibly empty replacement graph.
•I is the set of embedding instructions consisting of tuples of the form
((h,t,e),(h,r,f)),where
–h∈Σis a label of a node v ∈G\T,
–t∈Σis a label of a node w ∈VT,
–e∈Σis the label of the edge {v,w},
–f∈Σis another edge label not necessarily unequal to e, and
–r∈VRis a node in R.
1Labels are used to specify types and as variables for other labels. To avoid confusion,
variable labels will be denoted by capital letters, and all other labels with small let-
ters.
29
3 Graph Grammar Model for Design
An embedding instruction ((h,t,e),(h,r,f)) is interpreted as follows:
If there is an edge with label e connecting a node labeled h with the
target node t, then the embedding process will create a new edge with
label f connecting the node labeled h with node r. See section 3.4 for a
detailed discussion about the semantics of embeddings instructions.
The execution of a graph transformation rule p on a host graph G yielding
anewgraphG
is called a derivation step and denoted by G ⇒pG.A
sequence of such derivation steps is called derivation.
Remarks.
In many cases we will not need the complete expres-
sive power of the embedding instruction definition. If the target
graph consists of a single node and edge labels are left unchanged2,
then an embedding instruction may be written as (e,r)instead of
((h,t,e),(h,r,e)).
Example.
In order to illustrate how a graph transformation rule works,
let us view the transformation of a graph Ginto a graph G,asdepicted
in Figure 3.4.
G’G
a
bc
d e
fgf
Tn
ade
ff
R
Figure 3.4: Application of a context-free graph transformation rule on
ahostgraphGshowing a target graph Tand a replacement
graph R.
A graph transformation rule T→R,Ithat performs the transfor-
mation shown in Figure 3.4 has the following components:
2In the literature grammars that do not change edge labels in the embedding process
are called neighborhood uniform grammars.
30
3.2 Context-free Design Graph Grammar
•Target T=VT,ET,
σ
T={1, 2},{{1, 2}},{(1, b),(2, c)}
•Replacement R=VR,ER,
σ
R={3},{},{(3, n)}
•Set Iof embedding instructions with I={((a,b,f),(a,n,f)),
((e,c,f),(e,n,f))}. Alternatively, one can employ variable la-
bels, which yields I={((X,Y,f),(X,n,f))}.
In the following we present the formal representation of a simple
design graph grammar.
Example.
Let G=Σ,P,sbe a design graph grammar that comprises
some transformations described in section 3.1.
•Σ={?, A,B,C,D,low,high,pump,heater,mixer},
•P={r1,r2},
•s=?
Rule r1is defined as follows:
T={1, 2, 3},{(1, 2),(2, 3)},{(1, A),(2, ?),(3, B),
((1, 2),low),((2, 3),high)}
R={4, 5, 6, 7},{(4, 5),(5, 6),(6, 7)},
{(4, A),(5, pump),(6, heater),(7, B),
((4, 5),low),((6, 7),high)}
I={((D,A,E),(D,A,E)),((D,B,E),(D,B,E))}
The graphical representation of the above rule is:
Tlow Thigh TlowThigh
?
31
3 Graph Grammar Model for Design
The formal representation of rule r2is:
T={1, 2, 3, 4},{(1, 3),(2, 3),(3, 4)},{(1, A),(2, B),
(3, ?),(4, C),((1, 3),low),((2, 3),high),((3, 4),high)}
R={5, 6, 7, 8, 9, 10},{(5, 7),(7, 8),(8, 9),(6, 9),(9, 10)},
{(5, A),(6, B),(7, heater),(8, pump),(9, mixer),(10, C),
((5, 7),low),((6, 9),high),((9, 10),high)}
I={((D,A,E),(D,A,E)),((D,B,E),(D,B,E)),
((D,C,E),(D,C,E))}
The formal described above corresponds to the following graphical
notation:
Tlow Thigh Thigh
Thigh Thigh
Tlow
?
3.3 Context-sensitive Design Graph Grammar
In section 3.2 the notion of context-free design graph grammars was in-
troduced. However, it is conceivable that context-sensitive rules may
be necessary, which fact makes context-free graph grammars inad-
equate. In the literature, the natural extension of context-free graph
grammars is called context-sensitive graph grammars. The following def-
inition is based on definition 5of section 3.2.
Definition 6 (Context-sensitive Design Graph Grammar)
A context-sensitive design graph grammar is a tuple G=Σ,P,sas
described in definition 5, but where the productions of the set P are graph
transformation rules of the form T,C→R,Iwith
•T=VT,ET,
σ
Tis the target graph to be replaced,
32
3.3 Context-sensitive Design Graph Grammar
•C is a supergraph of T, called the context,
•R=VR,ER,
σ
Ris the possibly empty replacement graph.
•I is the set of embedding instructions.
The semantics of a graph transformation rule T,C→R,Iis as
follows: Firstly, a matching of the context C is searched within the host
graph. Secondly, an occurrence of T within the matching of C along
with all incident edges is deleted. Thirdly, an isomorphic copy of R is
connected to the host graph according to the semantics of the embedding
instructions.
The set I of embedding instructions consists of tuples of the form
((h,t,e),(h,r,f)), which are interpreted as in the context-free case.
In the following we will not always distinguish between both
graph grammar types, since this should be obvious from the context
and rule types.
Example.
In order to illustrate how a context-sensitive graph transfor-
mation rule works, let us view the transformation of a graph Ginto a
graph G, as depicted in Figure 3.5.
G
a
bc
d
T
C
f
g
a
n
d
R
C
f
g
G’
Figure 3.5: A context-sensitive graph transformation rule showing a
host graph G,atargetgraphT,acontextgraphCand a
replacement graph R.
33
3 Graph Grammar Model for Design
A graph transformation rule T,C→R,Ithat performs the
transformation shown in Figure 3.5 has the following components:
T=VT,ET,
σ
T={1, 2},{{1, 2}},{(1, b),(2, c)}
C=VC,EC,
σ
C{3, 4, 5, 6, 7, 8},{{3, 4},{3, 7},
{7, 8},{4, 8},{3, 5},{5, 6},{6, 8}},
{(3, a),(5, b),(6, c),(8, d),({3, 5},f),({6, 8},g)}
R=VR,ER,
σ
R={9},{},{(9, n)}
I={((a,b,f),(a,n,f)),((d,c,g),(d,n,g))}
Remarks.
Design graph grammars differ not only in matters of context,
but also as far as the size of the target graph of the graph transforma-
tion rules is concerned. If all target graphs of the graph transformation
rules consist of single nodes, then the graph grammar is called node-
based, otherwise it is called graph-based. This distinction is of relevance,
since node-based and graph-based graph grammars fall into different
complexity classes due to the subgraph matching problem (see 7.3.2)
connected to the latter.
Example.
The following simple3graph transformation rules depicted
in Figures 3.6,3.7 and 3.8 illustrate some cases where node-based
graph transformation rules are insufficient. Note that such rules are
required for optimization and repair purposes.
Figure 3.6: Replacement of a partial chain consisting of a mixer, a
pump and a heat transfer unit with a mixer device with
built-in heat transfer.
3For the sake of simplicity edge labels have been omitted.
34
3.4 On the Semantics of Labels
?
Figure 3.7: Removal of a superfluous nonterminal node.
Figure 3.8: Combination of two identical partial chains through relo-
cation. Depending on the properties of the substances in-
volved, a different mixer device has to be used.
3.4 On the Semantics of Labels
Labels are of paramount importance for the graph transformation pro-
cess, since all tasks belonging to a transformation step—matching of
target and context graphs, embedding of replacement graphs—rely on
them. Within this section we address some issues related to labels: ter-
minal and nonterminal labels, variable labels, ambiguities during em-
bedding, and conflicting embedding instructions.
3.4.1 Terminal and Nonterminal Labels
Several approaches distinguish between terminal and nonterminal
labels: terminal labels may appear only within the right-hand sides of
graph transformation rules; nonterminal labels are used within both
sides.
Design graph grammars use the classic concept of graph matching
and, therefore, there is no syntactical distinction with respect to termi-
nals and nonterminals in the set Σ. Note that this behavior reflects the
modeling structure of the domain.
35
3 Graph Grammar Model for Design
Furthermore, the above mentioned approaches also distinguish be-
tween terminal (or final) and nonterminal graphs—a graph is final if
it contains only terminal labels, otherwise it is nonterminal. Design
graph grammars do not make this distinction, since this is not always
possible or desirable in the technical domains focused.
3.4.2 Variable Labels
Variable labels are introduced for convenience purposes: They al-
low for the formulation of generic rules, which match situations be-
longing to identical topologies that differ with respect to their labels;
without variable labels one rule for each such situation would have to
be devised, leading to a large rule set due to the combinatorial explo-
sion.
Furthermore, the use of variable labels within rules and embed-
ding instructions leads to the question of “variable binding”. Firstly,
variables used exclusively within embedding instructions are used as
placeholders for concrete labels of nodes or edges matching the de-
scribed context; such variables are unbound. Secondly, variables may be
used within rules, i. e., within target, context and replacement graphs,
where they represent a specific instance; such variables are bound and
used uniformly throughout the rule application, i. e., the variable re-
tains its “value” during the replacement and embedding processes.
Note that variable labels prevent a clear distinction between ter-
minal and nonterminal labels: The labels in Σcan no longer be easily
classified into terminal or nonterminal by analysis of the graph trans-
formation rules in P.
In case conflicts within the embedding instructions arise due to the
use of variable labels, the principle of the least commitment shall apply:
The most specialized embedding instruction is to be chosen.
36
3.4 On the Semantics of Labels
3.4.3 Ambiguities
The design graph grammar approach, like the classical graph
grammars, relies mainly on node and edge labels to describe matches
and embeddings. Since nodes and edges may share identical labels,
ambiguities may occur, leading to possibly unwanted embeddings.
Ambiguities may stem from identical edge labels of edges connected
to one node or nodes with identical labels in the target graph, from
identical node labels in the replacement graph as well as from a com-
bination thereof. Figure 3.9 shows an example of such a situation.
ae
e
bc
e
e
I = {((H,a,e),(H,b,e)),
((H,a,e),(H,c,e))}
abc
Situation 1
Situation 2
bc
e
e
e
e
Figure 3.9: Graph transformation rule and two possible outcomes due
to ambiguity.
A straightforward solution to this problem is the numbering of
identical labels in order to make them unique. Please note that it suf-
fices to perform this numbering at the implementation level; this rem-
edy remains transparent to users.
37
3 Graph Grammar Model for Design
38
4 Analyzing Systems
In section 3we introduced the concept of graph grammars and ex-
plained how a design can be manipulated by means of a graph gram-
mar. In this section we present an approach that works reversedly: A
given design is analyzed by means of a suitable graph grammar (to-
gether with domain knowledge) in order to determine its feasibility.
Analysis by
Graph Grammars
Analysis by
Simulation Synthesis
(Repair/Optimization)
Synthesis by
Graph Grammars
Evaluation
Figure 4.1: The design cycle.
As depicted by Figure 4.1, the analysis of a system is part of the
whole design process, and it consists of two distinct steps that are dealt
with separately. The design processelementscanbedescribedasfol-
lows:
•Synthesis by Graph Grammars. Based on the specified inputs and
outputs and any further task requirements, a structure is built in
compliance with the design graph grammar used. The resulting
structure is feasible by definition, but at an abstract level.
•Analysis by Graph Grammars. This step is mainly concerned with
the analysis of the structure of the system, for which task graph
39
4 Analyzing Systems
grammars have proven to be very adequate. A given design
is analyzed with respect to its structure and type information,
which represents traits from the underlying model at an abstract
level. If a structure outstands this analysis step, then it is found to
be feasible, and analysis of the underlying model can be started.
•Analysis by Simulation. This step pertains to the underlying
model, i. e., the behavioral level, and takes the structure for
granted. The feasible structure is now brought to completion by
taking the underlying model into consideration. Simulation is
not performed at the abstract level, but at a lower level that is
closer to the physical representation. A design that withstands
this process is considered functional.
•Evaluation. A system design that has been found to be functional
may or may not fulfill the task demands properly. This step tries
to decide, according to some pre-specified criteria, if the given
design is acceptable or if it should be changed or improved.
•Synthesis (Repair, Optimization). If a design is incorrect or just not
fulfills all requirements, then some sort of adjustment must take
place. Here, constructive steps are performed to produce an im-
proved version of the original design. After completion, the de-
sign is passed to the next stage, analysis by simulation, to check
that the resulting design is indeed functional.
4.1 Structure Analysis by Graph Grammars
Structural analysis aims at a preliminary statement concerning the fea-
sibility of a given design of a technical system. This abstract feasibil-
ity check involves the design structure and the chosen components,
but refrains from delving into the details concerning the underlying
model, which are examined within the behavior analysis step. A de-
sign’s structure and choice of components can be derived by means
of design graph grammars that encode engineering knowledge. Thus,
it is logical to use a design graph grammar to perform this structural
analysis.
40
4.1 Structure Analysis by Graph Grammars
In order to use a design graph grammar to check the structural
feasibility of a given design, it is necessary to determine if the design
can be generated by the grammar—this problem is known as the mem-
bership problem for graph languages and is addressed in section 7.5.1.
In the case of string grammars, the membership problem is solved by
applying grammar rules in a backward fashion in order to derive the
initial symbol; for grammars in certain normal forms this procedure
is efficient (see section 7.5.1)—thus, an analogous approach is pur-
sued here. The successful derivation of the initial symbol means that
the given design belongs to the graph language generated by the de-
sign graph grammar, and the used graph transformation rules together
with the application order yield a valid inversed derivation.
The following steps summarize the process of structural analysis
by design graph grammars:
1. Invert the design graph grammar, i. e., change each graph trans-
formation rule T,C→R,Iinto R,I→T,C.
2. Choose an inverted graph transformation rule for application. If
no graph transformation rule is applicable, then the design is not
structurally feasible with respect to the design graph grammar
used.
3. Apply the chosen graph transformation rule to the design.
4. If the design consists of the initial symbol after application of the
graph transformation rule, then the given design is structurally
feasible, otherwise continue at step 2.
This abstract algorithm assumes that the order of application of
graph transformation rules is irrelevant and does not take backtrack-
ing into account, but can be improved to do so.
The following pseudo-code algorithm determines if a specific
graph is derivable with a given design graph grammar and corre-
sponds to the above abstract algorithm.
ANALYSIS-STEP
Input: An inverted design graph grammar Gand a graph G.
41
4 Analyzing Systems
Output:true, if the initial symbol could be derived, otherwise the re-
sulting graph is returned.
(1) ANALYSIS-STEP(DGG G,GRAPH G){
(2) if INITIAL-SYMBOL-P(G)then result := true;
(3) else {
(4) result := false;
(5) ruleapps := CHECK-MATCHINGS(G,G);
(6) while (ruleapps =∅and result = false){
(7) ruleapp := SELECT-RULE(ruleapps, G);
(8) ruleapps := ruleapps \{ruleapp};
(9) result := ANALYSIS-STEP(G,APPLY-RULE(ruleapp, G));
(10) }
(11) }
(12) return result;
(13) }
The algorithm ANALYSIS-STEP makes use of four subroutines:
1. INITIAL-SYMBOL-P. A predicate function that determines if a
graph Gcorresponds to the initial symbol. If not, INITIAL-
SYMBOL-Preturns false.
2. CHECK-MATCHINGS. A function that searches for all possible
matches of rules in Gwithin the graph G.
3. SELECT-RULE. A function that chooses a fitting rule according to
the search strategies implemented for the domain (see section
5.4 for some approaches tailored for the domain of chemical en-
gineering). This function has a direct impact on efficiency.
4. APPLY-RULE. A function that fires the chosen rule on the given
graph and returns the transformed graph.
In case this feasibilty check fails, i. e., the initial symbol cannot be
derived from the given design, some adjustments must be made to the
faulty context to make the design compliant with the underlying de-
sign graph grammar. Note that at this point only adjustments pertain-
42
4.2 Caramel Syrup Example
ing to node and edge labels are performed; any other changes involve
structural transformations, which belong to another step, design repair
and optimization.
Without applying any restrictions to the design graph grammar
and the generated graph language, the membership problem remains
NP-complete (see section 7.5.1) and the above algorithm will require
exponential time in the size of the design to determine if a given de-
sign belongs to the language generated by the design graph grammar.
The NP-completeness of this problem is partially due to the subgraph
matching problem described in section 7.3.2. The theoretical issues con-
cerning the time complexity of this membership test and the possible
restrictions that lead to a better performance are discussed in detail in
section 7.5.
4.2 Caramel Syrup Example
We shall now simulate the functioning of the above procedures to try
to determine if the design is feasible with respect to the used design
graph grammar, i. e., with respect to the structure.
The design graph grammar we shall use reflects the transforma-
tions depicted in the caramel syrup example of section 2.1. These trans-
formations are performed by rules (R1)through(R6). Furthermore, we
introduce additional rules as illustrated by Figures 4.8 and 4.9.
p p p
?
AB AB
Figure 4.2: (R1) Deletion of nonterminal node.
Now, rules (R1)through(R8) are used to derive the initial symbol,
which process is shown in Figure 4.10. The initial graph is the first
graph in the derivation chain.
Note that at certain points creative steps, which correspond to the
backward execution of destructive rules (such as (R1)), have to be taken
in order to be able to perform other reduction steps.
43
4 Analyzing Systems
?
sn
s3...
s1
s2
A
B
?
sn
s3...
s1
s2
A
B
Figure 4.3: (R2) Insertion of a mixing unit-op.
?
sn
s3...
s1
s2
A
B
?
sn
s3...
s1
s2
A
B
Figure 4.4: (R3) Insertion of mixing unit-op with built-in heat transfer
unit.
?
sliquid
ssolid
sliquid ?
?
sliquid
sliquid
ssolid
A
B
C
A
B
C
Figure 4.5: (R4) Improvement of mixing properties by handling solid
inputs separately.
tlow
thigh
thigh
tlow thigh
thigh
??
A
B
CA
B
C
Figure 4.6: (R5) Improvement of dissolving properties by heating an
input.
44
4.3 Behavior Analysis by Simulation
ptptpt
? ?AA
Figure 4.7: (R6) Insertion of a pump unit-op.
thigh
tlow
thigh
tlow
??
?
tlow
tlow
A
B
C
A
B
C
Figure 4.8: (R7) Improvement of mixing properties by handling inputs
of different temperatures separately.
thigh
tmed
tmed
tmed
thigh
?
?
A
B
A
B
Figure 4.9: (R8) Improvement of dissolving properties by cooling an
input.
4.3 Behavior Analysis by Simulation
In the previous section the feasibility of the design’s structure was
checked. This fact, however, does not imply a functional design—it
only means that the structure is feasible and that it may belong to a
functional design. It is not even guaranteed that this structure is suit-
able to solve the task at hand.
Thus, another procedure that goes a step further is necessary to de-
cide on a design’s functionality: simulation. Now, the feasible structure
is enriched with further information pertaining to the chosen devices
and involved substances, i. e., we move our focus to the underlying
45
4 Analyzing Systems
tlow
tlow
thigh
tmedium
tmedium
tmedium
R1
tlow
?
tlow
thigh
tmedium
tmedium
tmedium tmedium
R2?
tlow
tlow
thigh
tmedium
tmedium
tmedium
R8?
tlow
tlow
thigh
tmedium tmedium
R1
?
tlow
tlow
thigh
tmedium
tmedium
R3?
?
tlow
tlow
thigh
tmedium R7?
thigh
tmedium
tlow
tlow
?
Figure 4.10: Derivation of the initial symbol.
46
4.3 Behavior Analysis by Simulation
model. At this level, a reliable statement concerning a design’s func-
tionality can be derived.
Before our simulation approach is presented, we shortly describe
the traditional simulation approaches followed by other systems and
compare them to our situation.
4.3.1 Classical Simulation
Existing systems, as described in [Marquardt,1996], have in com-
mon that they somehow produce a mathematical model—the under-
lying model—of the system to be simulated. Then, this mathematical
model is transformed into input for a numerical algorithm, which tries
to solve the equations.
The generation of the mathematical model is done either manually,
as in equation-oriented systems, or partially automatically, as in block-
oriented systems. In either way the plant design is decomposed into
its parts, for which mathematical relations are given, and these math-
ematical relations are connected to each other, providing a model at
which level the plant is simulated. Figure 4.11 illustrates this process.
Analysis by
Graph Grammars
Analysis by
Simulation Design
Evaluation Synthesis
(Repair/Optimization)
Synthesis by
Graph Grammars
Device
Decomposition Model
Synthesis Model
Simulation
Figure 4.11: Steps belonging to simulation of a system.
47
4 Analyzing Systems
These steps can be described in the following way:
•Device Decomposition. This step encompasses the retrieval of the
mathematical relations describing the physical properties be-
longing to the separate devices. At this stage these mathemati-
cal relations are collected independently and not coupled in any
manner.
•Model Synthesis. The mathematical relations collected in the pre-
vious step are coupled to form a model describing the system
at hand. This step corresponds to a nontrivial process that re-
quires, depending on the modeling depth, a large degree of do-
main knowledge.
•Model Simulation. Within this phase the equation system derived
in the last step is solved, yielding results that have to be evalu-
ated in order to decide on the plant’s functionality or any neces-
sary corrections.
4.3.2 Qualitative Simulation
The underlying model of our approach, in contrast to the struc-
ture generated by the graph grammar, is not abstract, but closer to the
physical level. This means that at this level we no longer deal with sim-
plified substance properties or abstract device families, but with crisp
substance values and concrete device parameters. However, we still
restrain ourselves from actually working at the physical level, which
implies dealing with differential equations, numerical algorithms etc.
like the traditional approaches. For our approach the steps belonging
to the simulation phase could be described as follows:
•Device Decomposition. This step consists of the transition from
the abstract level to the concrete parameter level. Every abstract
device representation is enriched with the concrete parameters,
transforming it into a concrete device. As in the case of tradi-
tional systems, this is an information retrieval step.
48
4.3 Behavior Analysis by Simulation
•Model Synthesis. In contrast to the model synthesis of traditional
systems, we take the design’s structure as a basis to combine the
concrete devices.
•Model Simulation. Instead of solving complex mathematical equa-
tions, model simulation here consists of the execution of func-
tions representing the different transformations performed by
the devices and the propagation of these results throughout the
structure.
Remarks.
In contrast to most traditional approaches, we work solely at
the device level. Put in other words, we regard devices as atomic and
do not perform any further decomposition, i. e., devices are not broken
down into components that do not represent or perform any essential
function.
Also note that within the domain of chemical engineering a mathe-
matical model of a plant design may not exist at all—some aspects still
lack a mathematical model and are regarded as black boxes.Sinceour
simulation approach works at a higher level, usable results may still
be produced.
4.3.3 Complexity of Design Evaluation
As argued in section 5.3, the graphs generated by our approach are
topologically restricted—they lack cycles, are directed, and generated
by means of mostly context-free rules. Thus, the time complexity to
simulate a generated design is linear in the number of nodes, since
a topological search is sufficient to visit all nodes in the appropriate
order.
Taking the computational effort for the simulation of a device into
account, the total computational effort amounts to O(n·D),whereD
is the maximum effort necessary to simulate a device.
49
4 Analyzing Systems
50
5 Synthesizing Systems
In section 3we presented a brief introduction to graph grammars,
which, depending on their type, provide the necessary mechanisms to
solve various design tasks, which are depicted in Figure 5.1.Nowwe
give an overview of the synthesis approach, which pursues the goal
of generating a system from scratch. Additionally, we address some
issues and introduce some enhancements to improve and accelerate
search.
Analysis by
Graph Grammars
Analysis by
Simulation Synthesis
(Repair/Optimization)
Synthesis by
Graph Grammars
Evaluation
Figure 5.1: The design cycle.
Remarks.
Note that by synthesis we mean the generation of designs,
including structure definition, choice of abstract devices and model
synthesis. Due to model simplification, such a generated design may
not fulfill the demands properly, making some repair or optimization
steps necessary. Repair and optimization, although implying synthesis
steps, are not dealt with here, but in chapter 6.
51
5 Synthesizing Systems
5.1 Structure Synthesis by Graph Grammars
In section 2.1 we described the part of the design process that is re-
sponsible for structure generation, and in section 2.2 the generation of
the underlying model was addressed, together with some other topics
such as optimization. Here we concentrate on the structure synthesis,
i. e., we care only for the graph grammar related part of the synthesis
process.
The synthesis of a chemical plant structure is, as mentioned previ-
ously, based on the given input and the desired output. Thus, the gen-
eration process begins with an abstract design represented by a single
nonterminal node to which edges describing the given inputs and the
desired output are connected. The simple algorithm described below
reflects this idea.
SYNTHESIS-STEP
Input: A design graph grammar Gand an initial graph G.
Output: A graph consisting of terminal nodes or the symbol fail.
(1) SYNTHESIS-STEP(DGG G,GRAPH G){
(2) if TERMINAL-P(G)then result := G;
(3) else {
(4) result := fail;
(5) rules := CHECK-MATCHINGS(G,G);
(6) while (rules =∅and result = fail){
(7) rule := SELECT-RULE(rules, G);
(8) rules := rules \{rule};
(9) result := SYNTHESIS-STEP(G,APPLY-RULE(rule, G));
(10) }
(11) }
(12) return result;
(13) }
The algorithm SYNTHESIS-STEP makes use of four subroutines:
1. TERMINAL-P. A predicate function that determines if a graph G
is terminal, i. e., if Gcontains any nodes labeled with “?”. If not,
52
5.2 Caramel Syrup Example Reviewed
TERMINAL-Preturns true.
2. CHECK-MATCHINGS. A function that searches for all possible
matches of rules in Gwithin the graph G.
3. SELECT-RULE. A function that chooses a fitting rule according to
the search strategies implemented for the domain (see section
5.4 for some approaches tailored for the domain of chemical en-
gineering). This function has a direct impact on efficiency and
design quality.
4. APPLY-RULE. A function that fires the chosen rule on the given
graph and returns the transformed graph.
5.2 Caramel Syrup Example Reviewed
In section 2we described the design procedure for a caramel syrup
process and presented a solution to this problem from the point of
view of an engineer. Now, we will use a graph grammar to attain the
same goal. For this purpose, the graph rules depicted by Figures 4.2 –
4.7 in section 4.2 are given. Finally, Figure 5.2 shows a derivation that
produces a feasible design.
In general there will be a series of rules that apply for a given sit-
uation (i. e., setential form), leading to different solutions of varying
quality and cost. Thus, the generation process can be viewed as a tree
containing derivations for all possible alternatives, as shown in Figure
5.3. Note that the graph grammar derivation of Figure 5.2 corresponds
to one branch of this tree.
Finally, the structure generated is completed into a design by
adding the information from the underlying model to the abstract
layer. At this point, the synthesis process is finished. Subsequent sim-
ulation and evaluation steps decide if the proposed design fulfills the
demands adequately or if it requires some adjustments to do so.
53
5 Synthesizing Systems
?
Starch
syrup
Water
Sugar
Caramel
syrup
R4
Starch
syrup
Water
Sugar
?
?Caramel
syrup
Starch
syrup
Water
Sugar
Caramel
syrup
Starch
syrup
Water
Sugar
?Caramel
syrup
Starch
syrup
Water
Sugar
?Caramel
syrup
Starch
syrup
Water
Sugar
?Caramel
syrup
Starch
syrup
Water
Sugar
?
?Caramel
syrup
R5
R2, R1
R6
R5
R3, R1
Figure 5.2: Derivation of the caramel plant design.
54
5.3 Graph Topology Restrictions
Cost: 120
Cost: 140
Cost: 90
...
...
...
?
Figure 5.3: Search tree for the optimization of the design generation
process.
5.3 Graph Topology Restrictions
In practice, plants often combine various chemical processes within
one single “chain” producing one main product and several by-
products. This means that the topology represents a directed acyclic
graphoragraphofevengreatercomplexity;graphsofsuchcom-
plexity can only be generated by graph-based graph grammars, which
imply exponential time complexity, as rules may have more than one
nonterminal on the left-hand side (subgraph matching problem, see
[Garey and Johnson,1997]). In order to avoid this drawback, we re-
strict, as far as possible, the set of graph production rules to context-
free rules, which generate a graph in polynomial time [Brandenburg,
1994].
Another restriction that has already been discussed in section 1.3
is enforced by avoiding cycles within a design. Cycles not only hin-
der an efficient graph grammar processing, but also make simulation
more complicated. Through causal decomposition the expected time
complexity can be substantially reduced.
55
5 Synthesizing Systems
These restrictions have far-reaching implications for both system
synthesis steps. On the one hand they guarantee a better performance
due the simplifications imposed by the restrictions, while on the other
hand they rule out certain complex structures and more exact simula-
tion results.
5.4 Search Techniques
The search for a solution of a design task corresponds to the search
of a design graph grammar derivation whose final graph meets the
imposed requirements. A final graph does not contain any unspeci-
fied nodes—initially existing unspecified nodes are either replaced by
specified nodes or deleted if the input and output edge labels are iden-
tical, i. e., the unspecified node represents the identity mapping. How-
ever, a final graph that meets the task requirements does not necessar-
ily represent a good solution; therefore, the search process has to take
alternatives into consideration.
Design graph grammars represent a mechanism for the descrip-
tion of the synthesis search space—they define the allowed transfor-
mations, thereby specifying the possible solutions attainable with this
concept. They do not provide any means to efficiently search for the
best solution for a given design task.
Due to model simplification the search space spawned by design
graph grammars is indeed small in comparison to the unrestricted so-
lution space of the given domain. However, even this small solution
space cannot be efficiently searched with naive methods: Depth-first-
search with backtracking may not terminate in case there are infinite
branches; breadth-first-search leads to inefficiency in terms of mem-
ory usage and running time; even iterative deepening does not appear
very promising. For example, a small design graph grammar with 10
always applicable graph transformation rules spawns a small search
space containing 1.000.000.000 graphs at a depth of 9. Therefore, in-
telligent techniques are required in order to improve the search for a
solution. Figure 5.4 illustrates the search space problem.
56
5.4 Search Techniques
Figure 5.4: Simplified search space as described by design graph
grammars.
In the following we present some ideas that lead to highly efficient
search in the graph space spawned by design graph grammars. Note
that these techniques may be applied independently or in a combined
fashion.
5.4.1 Label Ordering
Design graph grammars, as introduced in section 3,performtrans-
formations based mainly on node and edge labels. Depending on the
domain, these labels may be exploited in order to direct the search for
a solution; here, the domain of chemical engineering shall help to il-
57
5 Synthesizing Systems
lustrate this idea.
Design graph grammars for the domain of chemical engineering
rely heavily on edge and node labels to specify application contexts.
Within this domain, as indicated in chapter 2, node labels designate
functions that are performed on substances that are represented by
edge labels. To be more precise, edge labels describe the properties of
the substance conveyed through an edge.
Substance properties are ordered, since most properties represent
a value on some scale, such as temperature, density, or viscosity. Thus,
in our simplified world, there are labels tlrepresenting a low temper-
ature, tma medium temperature and tha high temperature. Likewise,
there are labels vl,vm,andvhfor viscosity, dl,dm,anddhfor density and
so on. Formally speaking, there is a function succ :Σ→Σthat, when
applied to a given label, yields the successor of this label with respect
to the given label ordering. Thus, succ(tl)=tm,succ(succ(tl)) = th,
succ(th)=thand so on. Furthermore, the distance between two la-
bels can be given by another function dist :Σ×Σ→N,where
dist(l1,l2)=kmeans that ksucc–operations are required to achieve
equality, i. e., a distance of 0. Note that this function can be enhanced
to deal with combined labels of the form tlvh.
With help of label ordering, one can now perform a more directed
search for a solution within the graph space. At any given point within
an incomplete derivation, a set Aof applicable graph transformation
rules representing the possible choices is given. Now, the application
context for any given graph transformation rule includes a set of input
edge labels and a set of output edge labels, which, in the chemical en-
gineering case, contains a single element. These input and output edge
labels reflect the “before-after” situation.
At this stage the potential result of the application of a graph trans-
formation rule of the set Ato the given context is examined with re-
spect to the gain in terms of label distance. The graph transformation
rule that minizes the label distance is chosen for application. Note that
the effect of a graph transformation rule on the resulting label distance
can be determined a-priori.
58
5.4 Search Techniques
Figure 5.5 illustrates the use of label ordering.
tlow thigh
tlow thigh
??AC
AC
tmed
Figure 5.5: A graph transformation rule that reduces the label distance
by 1 unit.
Remarks.
Label ordering is suitable to guide the search process in local
terms. Depending on the task at hand, this approach will not lead to a
good solution in global terms; for instance, an optimum chemical plant
for a given task may have to apply heating and cooling repeatedly, i.
e., labels do not necessarily change monotonously.
In other domains in which edge labels do not play a major role (or
any role at all), this approach may not be used. In such cases one has
to resort to one of the other search optimization techniques.
5.4.2 Reinforcement Learning of Rule Priorities
Graph transformation rules are used to different degrees in design
tasks—some rules performing essential transformations are applied
often, others are rarely fired because they deal with unusual situations.
In any case, it is a logical assumption that graph transformation rules
are of varying importance for design tasks. This knowledge can be ex-
ploited to speed up the search process by assigning priorities to the
graph transformation rules.
On the one hand, the expert may have some favorite operations or
some type of ranking determining the most useful rules. In this case
the expert may assign priorities to the graph transformation rules he
formulates. It should be noted that manually assigned priorities reflect
the preferences of one expert; such priorities may not correspond to the
view of a group of experts. On the other hand, an a-priori assignment
of priorities may not be possible, for instance due to the size of a rule
set, incomparability of rules or strong similarity between rules.
59
5 Synthesizing Systems
Experts become experts through experience they accumulate dur-
ing their lifetimes. This means that, initially, experts know very little
about rule priorities; they amass this knowledge with time. Similarly,
the search process can learn about rule priorities incrementally: Each
design task is connected to a set of rules that are applied to achieve the
solution; these graph transformation rules are then “rewarded” with
an increase in priority, leading to a preferred application of these rules
in future design task solution processes. This rewarding technique is
usually known as reinforcement learning.
Remarks.
The reinforcement learning approach can lead to the exclu-
sive use of a subset of the available graph transformation rules. For
instance, this phenomenon occurs if there are different rules for the
same purpose. However, this must not be a disadvantage, since rules
that are never used are probably superfluous.
5.4.3 Model Compilation
Another way to improve the search for a solution is to preprocess
the search space. The idea behind this preprocessing phase is to collect
information on the search space so that subsequent searches for spe-
cific solutions will be found as fast as possible. Such a preprocessing
procedure is called model compilation [Stein,2001]; Figure 5.6 illustrates
this idea.
Beginning with a set Dof demands, the search space is examined
thoroughly in order to find a solution. At any given solution the path
leading back to the starting point is evaluated by means of regression;
each choice point belonging to this path is reevaluated (choice points
may belong to more than one solution path) in accordance with a set of
features chosen for this specific domain. Each choice point is assigned
a value between 0 and 1 which designates its success probability, lead-
ing to a well directed search.
Remarks.
The compilation of the search space is an exhaustive job that
takes considerable time—among other resources—to be done, depend-
ing on the design graph grammar used, the maximum search depth,
60
5.4 Search Techniques
Choice point
Features
Figure 5.6: Compiled search space: Choice points represent graphs to-
gether with features.
and the number of representative tasks required. Besides, since graph
grammar derivations may be endless due to loops, a restriction of the
maximum depth to be searched is compulsory.
A positive aspect of search space compilation is that the process
can be parallelized: Different machines examine and evaluate different
subtrees of the search space, or they search for solutions of different
design tasks. Overlapping results can be combined after all branches
have been examined independently.
The search techniques introduced above may be used in a unified
61
5 Synthesizing Systems
manner—if applicable—by means of a function staking the results of
the different search strategies into account. Let G=Σ,P,sbe the
design graph grammar in use, A={r1,...,rn}the set of currently
applicable rules with A⊂P,andsX:P→[0, 1]the search strategy
evaluation function for each X∈{ordering, priority, compilation};
then, we define the function s:P→[0, 1]as follows:
s(rk)=w1·sordering(rk)+w2·spriority(rk)+w3·scompilation(rk)
Additionally, it must hold that ∑i∈{1,2,3}wi=1. Also observe
that this linear combination can be easily extended to include further
search strategies.
62
6 Design Language
Design repair or optimization is necessary in many cases: Design gen-
eration typically produces, due to the simplifications applied to the
model, faulty designs requiring some adjustments to become feasible;
simulation of manually created designs often reveals deficiencies that
must be overcome by means of repair operations; and in some situa-
tions designs of technical systems may be optimized to reach higher
efficiency and lower costs. A design language in which repair and op-
timization knowledge is formulated can easily tackle these problems.
Figure 6.1 shows the areas of the design cycle affected by repair and
optimization by means of a design language.
Analysis by
Graph Grammars
Analysis by
Simulation Synthesis
(Repair/Optimization)
Synthesis by
Graph Grammars
Evaluation
Figure 6.1: The design cycle.
In the following we address the requirements that must be fulfilled
by a design language as well as a necessary enhancement of the design
graph grammar concept. A concrete design language is not presented
here—the fulfillment of this task belongs to future work.
63
6 Design Language
6.1 Requirements
In this section we address some issues that arise within the context of a
design language for repair and optimization of technical systems: the
types of possible modifications that are available and the search for
appropriate modification application contexts.
6.1.1 Modification Types
As stated above, the design language shall provide means to
formulate repair and optimization transformations, which are only
needed if some type of fault or insufficiency is detected. Hence, the
most important construct of the design language will be of the form
observation →adjustment,or,putinotherwords,symptom →remedy,i.
e., rules compose the main part of the design language.
There are different types of modifications for different types of
symptoms [Stein and Vier,1998], which differ in their gravity and
range of context:
•Local modifications. Local modifications are component-based, i.
e., they apply changes to a single component, modifying its be-
havior, and ignore the component’s neighborhood. We differen-
tiate between the following two local modification types:
–Parameter modification. This type of modification is equiva-
lent to a simple change of a parameter setting, like increas-
ing the power throughput or changing the dimensions of
the vessel of a mixer.
–Characteristics modification. This type of modification is more
radical in nature and corresponds to a replacement of a de-
vice with another, more fitting device. This modification is
only necessary if a parameter modification fails to correct
the problem.
•Global modifications. Global modifications are related to non-
locatable symptoms, i. e., symptoms that are not bound to a spe-
64
6.1 Requirements
cific component but to the system as a whole. These modifica-
tions require changes to the system topology by means of ad-
dition, deletion or reordering of components. Note that such a
modification may correspond to a change of characteristics (lo-
cal modification due to a non-locatable fault).
6.1.2 Modification Location
The most important issue concerning design repair and optimiza-
tion is, as observed in [Stein and Vier,1998], determining where amod-
ification is to occur. Obviously, the difficulty to find the modification
location depends on the symptom detected—if the fault is component-
based, then the location is known; if the fault is non-locatable, then the
location for the modification must be searched.
Stein and Vier introduce the notion of location specifiers for their de-
sign language [Stein and Vier,1998]. A similar mechanism is also re-
quired for our design language, but, instead of adding a new concept
to our approach, we resort once again to graph grammars. To this avail,
we allow the formulation of repair rules as tuples of the form “(Fault
Candidate, Modification, Additional Actions)”, where
•fault candidate is the location description of a possible modifica-
tion site and represents the left-hand side of a rule,
•modification describes the change to be applied and represents
the right-hand side of a rule, or may be empty, i. e., nothing is
changed,
•and additional actions are low level—or domain specific—actions
to be performed together with the graph transformation and are
required for parameter settings etc. This mechanism is required
to manipulate the underlying model of the design.
Now, instead of performing a search for the fault candidates
within the faulty design, the graph grammar’s rule-based behavior
is exploited. For every symptom a set of remedy rules is built and
65
6 Design Language
activated—the search is then performed by the rule processing engine.
After one rule has fired, the design has to be simulated once again in
order to check if the problem has been solved; if the fault persists or
another fault emerges, then the process is reiterated.
6.2 Semantics of Graphical Representation
The graph grammar model introduced in chapter 3is actually perfectly
suited for any conceivable transformation necessary within the scope
of design generation, system analysis or design repair and optimiza-
tion. However, the classical graphical representation of graph transfor-
mation rules is not able to reflect the use of some special features of de-
sign graph grammars. Additionally, we introduce some new graphical
features that aim at a better understanding of the graph transformation
rules.
One such aspect pertains to the edges incident to a target node. In
many cases only a subset of the incident edges is of interest, the re-
maining edges are irrelevant. By means of the embedding instructions
one can ascertain that these irrelevant edges are restored; however, this
is not visible within the graphical representation used so far. Thus, we
introduce a new graphical representation for such cases: A dotted edge
represents any number of edges that may exist beyond the ones speci-
fied explicitly. In order to improve readability, the graph rule designer
may also add labels to such edges, such as 0..nor s1,...,sm; however,
these labels do not have any further meaning for the rule application
process.
Apart from the dotted edges described above, we also allow the
graphical representation of labeled “dangling edges” when appropri-
ate. These edges do not interfere with the matching process and are
only relevant for the embedding step. The purpose of this “feature”
is to improve readability and stress the importance of these edges for
the embedding process. In most cases we will refrain from drawing
labeled dangling edges.
Another aspect that has not been addressed yet is the edge label
66
6.2 Semantics of Graphical Representation
complexity allowed. Within our approach, edge labels correspond to
abstract substance properties, such as vhtlwhich means “viscosity high
and temperature low”. Depending on the number of properties a label
has to encompass, a large number of combinations may be the result.
Thus, we allow rule edges to match host graph edges whose labels are
subsumed by the rule edge labels.
Figure 6.2 illustrates the use of template edges and label subsump-
tion.
cold-solid
hot-liquid
warm-liquid
solid
liquid
liquid
liquid
solid
liquid
solid
liquid
Figure 6.2: Rule with and two possible matches.
Finally, we allow the use of different node representations. In gen-
eral, nodes are depicted by circles, and their labels are placed outside
the circle. Although this representation is sufficient for our needs, the
use of specific graphical symbols representing devices of a concrete
domain is acceptable; in fact, such graphical symbols correspond to
a combined representation of nodes together with their type defining
labels. Note that we also allow the mixed use of graphical representa-
tions.
67
6 Design Language
6.3 Caramel Syrup Example Reviewed Again
We now take a further look at the caramel syrup example, whereas
emphasis is now laid on the synthesis-simulation-evaluation cycle and
not on one step alone. For the sake of simplicity, we assume there is
only a single fault that has to be corrected, limiting the number of cycle
iterations to one.
The design steps undertaken for the solution of the caramel syrup
task are1:
1. Demands. Instead of using relative mass values, as in section 2.1,
we now give concrete amounts: 15kg sugar, 45l water and 40l
starch syrup.
2. Synthesis. The synthesis consists of the generation of a structure,
based on the given demands, and the enhancement thereof with
concrete device data, which represents the underlying model.
a) Structure generation.
Structure
Generation
Starch
syrup
Water
Sugar
Caramel
syrup
sstl
sftlvl
sftlvm
sfth
Starch
syrup
Water
Sugar
Caramel
syrup
sstl
sftlvl
sftlvm
sfthvm
sfthvmsfthvm
sfthvlsfthvlsfthvmsfthvm
?
Figure 6.3: Generation of the caramel syrup design structure.
Figure 6.3 shows the structure resulting from the generation
process. Note that during the generation process label items
1The edge labels are: tfor “temperature”, vfor “viscosity”, and sfor “state”. The sub-
scriptsarequalifiersandmean:sfor “solid”, ffor “fluid”, gfor “gas”, lfor “low”, m
for “medium”, and hfor “high”.
68
6.3 Caramel Syrup Example Reviewed Again
may be appended to an existing label, and that the opposite
does not occur.
b) Behavior model generation.
Figure 6.4 shows the generated structure together with an
excerpt of the underlying model.
Starch
syrup
Water
Sugar
Caramel
syrup
[0-50C]
[0-50C]
45l
40l
15kg
[0-0.5 m3/h]
[0-0.5 m3/h] Propeller
Propeller
[0-0.5 m3/h]
100l
Figure 6.4: Caramel syrup design structure with underlying model in-
formation.
3. Simulation. Now, substance and mixture values and the results of
the functions performed by the devices are propagated through-
out the design structure, as shown in Figure 6.5.
Starch
syrup
Water
Sugar
Caramel
syrup
[0-50C]
[0-50C]
40l
15kg
[0-0.5 m3/h]
[0-0.5 m3/h]
[0-0.5 m3/h]
20C
20C
70C
70C
70C, ≤0.2Pas
70C, ≤0.001Pas
Propeller
≈ 65-70C
≈ 4Pas
Propeller
75% Solution
≈ 60-70C
≈ 30Pas
100l
≈ 65-70C
≈ 4Pas
45l
Figure 6.5: Simulation of the caramel syrup design: propagation of
properties and values.
69
6 Design Language
4. Evaluation. The results of the simulation and the task require-
ments are compared to determine if the actual design fulfills the
demands adequately. The first (and in our case only) observa-
tion is that the output, as produced by our design, is not hot
enough—the required output temperate was 110°C, i. e., the out-
put needs to be heated by at least 45°C. The following repair ac-
tions compose the actual choice list for this situation:
•Increase the power of one or more heat transfer units (pa-
rameter modification).
•Replace one or more heat transfer units with more power-
ful devices; alternatively, replace an agitator with one con-
taining a built-in heat transfer device (characteristics modifi-
cation).
•Insert an additional heat transfer unit to the design (global
modification).
In the present case a parameter modification is not possible, since
the heat transfer units are already working at maximum power
(∆t=50°C). The next simplest change would be the replacement
of a device—we choose to use an agitator with a built-in heat
transfer unit, as shown in Figure 6.6.
If a repair step was necessary, then the process continues with
the simulation step, otherwise the design is considered feasible
and the design cycle is interrupted here.
70
6.3 Caramel Syrup Example Reviewed Again
Starch
syrup
Water
Sugar
Caramel
syrup
[0-50C]
[0-50C]
45l
40l
15kg
[0-0.5 m3/h]
[0-0.5 m3/h]
[0-0.5 m3/h]
20C
20C
70C
70C
70C, ≤0.2Pas
70C, ≤0.001Pas
Propeller
75% Solution
≈ 60-70C
≈ 30Pas
100l
≤ 110C
≈ 4Pas
Propeller
Range: [0-50C]
≤ 110C
≈ 4Pas
Figure 6.6: Repaired caramel syrup design showing values after sim-
ulation.
71
6 Design Language
72
7 Classes, Complexity and Design
Evaluation
The development and use of design graph grammars (DGGs) is con-
nected to various theoretical issues, which are addressed in this chap-
ter, which is organized as follows.
Section 7.1 examines the relationship of design graph grammars to
the classical graph grammar approaches and establishes a language hi-
erarchy. Additionally, hybrid approaches and programmed graph re-
placement systems are addressed.
In sections 7.3,7.4 and 7.5 topics relevant for analysis are ad-
dressed: Subgraph matching and its consequences, complexity reduc-
ing properties, and special graph grammar classes, for which the mem-
bership problem can be solved in polynomial time. Figure 7.1 shows
the different concepts and their relationships to each other.
Membership Rule application Matching
Associativity, Confluence
⇑
Leftmost,
Boundary
Rooted flowgraph,
Precedence graph
Special grammars
Special properties
Derivation from
s
Analysis of
G
~
Is based on
Simplifies
Figure 7.1: Concepts, properties and special classes contributing to the
analysis of a design G.sdenotes the initial symbol of a
graph grammar (figure from [Stein,2001]).
73
7 Classes, Complexity and Design Evaluation
Furthermore, in section 7.5 issues concerning design quality are
also examined. Figure 7.2 presents an overview of the concepts and
properties necessary for a statement concerning the quality of a given
design.
Distance Shortest derivation from
s
~
Derivation from
G*
Quality of
G
~
Monotonicity,
Shortcut-free
Special properties
Is based on
Disambiguates
Figure 7.2: Concepts and special properties necessary for a statement
regarding the quality of a design G.G∗denotes the opti-
mum design, sdenotes the initial symbol of a graph gram-
mar (figure from [Stein,2001]).
7.1 Relationship Between Classical Graph Grammars and
Design Graph Grammars
An important question pertains to the justification of the development
of design graph grammars, which represent a further graph trans-
formation formalism amidst numerous existing graph grammar con-
cepts. In the following we describe the two general approaches to
graph transformation together with their most prominent graph gram-
mar representants and point out their advantages and disadvantages.
Some attention is also paid to hybrid concepts, which try to combine
the aforementioned approaches. We then compare design graph gram-
mars with the classical graph grammars and establish their relation-
ship. Finally, the relationship between design graph grammars and
programmed graph replacement systems is addressed.
74
7.1 Classical and Design Graph Grammars
7.1.1 The Connecting Approach
The connecting approach is a node-centered concept that aims at
the replacement of nodes or subgraphs by graphs. The item to be re-
placed is deleted along with all incident edges, and the replacement
graph is embedded into the host graph by connecting both with new
edges. These new edges are constructed by means of some mechanism
that specifies the embedding.
In the literature graph grammars are often distinguished by the size
of the left-hand sides of rules, leading to two approaches of inherently
different complexity: node replacement and graph replacement graph
grammars (called node-based and graph-based). Additionally, each of
these two approaches is divided into context-free and context-sensitive
subclasses.
Several graph grammars follow the connecting approach. Accord-
ing to [Engelfriet and Rozenberg,1997], the most well-known node re-
placement graph grammar families are the node label controlled (NLC)
and the neighborhood controlled embedding (NCE) graph grammars,
whose node-based versions we describe in the following.
NLC Graph Grammars
Node label controlled graph grammars perform graph transforma-
tions on undirected node-labeled graphs. A graph transformation step
is based merely on node labels, i. e., there are no application conditions
or contexts to be matched. The embedding is determined by a set of
embedding instructions shared by all graph transformation rules. The
following definition resembling the one of [Engelfriet and Rozenberg,
1997] introduces NLC grammars formally1.
Definition 7 (NLC Graph Grammar)
A NLC graph grammar is a tuple G =Σ,P,I,swith
1In the literature it is usually distinguished between different label alphabets. For the
sake of simplicity, we use one single alphabet including all necessary label types.
75
7 Classes, Complexity and Design Evaluation
•Σis the set of nonterminal and terminal labels,
•P is the finite set of graph transformation rules or productions of the
form t →R, where t ∈Σand R is a labeled graph,
•I is an embedding relation,
•s is the initial symbol.
Each embedding instruction (h,r)states that the embedding process
should create an edge connecting each node of the replacement graph labeled
r with each node of the host graph labeled h that is a neighbor of the target
node.
Remarks.
A graph transformation rule t→Rcan be applied to any
node labeled t, regardless of its context.
The domain of technical systems imposes a series of requirements,
of which some cannot be met by NLC grammars due to weaknesses of
this mechanism:
1. There is no way to specify a context. Therefore, it is not possi-
ble to distinguish between different situations related to a single
item.
2. There is no way to distinguish between individual nodes in the
replacement graph, since the embedding mechanism relies solely
on labels.
NCE Graph Grammars
Neighborhood controlled embedding graph grammars, an extension
of NLC grammars, perform graph transformations on directed or
undirected labeled graphs2. A graph transformation step is based on
2In the literature, NCE grammars with and without edge labels and edge directions are
distinguished by prefixes “e” (for edge labels) and “d”(for directed edges) that are
added to the NCE acronym. Thus, there are NCE, eNCE, dNCE and edNCE graph
grammars. For the sake of simplicity, we omit these prefixes.
76
7.1 Classical and Design Graph Grammars
node labels and edge labels, which provide further discerning power.
The embedding is determined by means of a set of embedding instruc-
tions associated with each graph transformation rule. The following
definition based on [Engelfriet and Rozenberg,1997] introduces NCE
grammars formally.
Definition 8 (NCE Graph Grammar)
An NCE graph grammar is a tuple G =Σ,P,swith
•Σis the alphabet of node and edge labels, and includes terminal and
nonterminal labels,
•P is the finite set of productions,
•and s is the initial symbol.
The productions of the set P are tuples of the form t →R,Iwith
•t∈Σis the label belonging to a node v in the host graph,
•R=VR,ER,
σ
Ris the non-empty replacement graph,
•I is the set of embedding instructions for the replacement graph R and
consists of tuples (h,e/f,r),where
–h∈Σis a node label and e ∈Σis an edge label in the host graph,
–f∈Σis another edge label,
–and r ∈VRis a node of the replacement graph.
An embedding rule (h,e/f,r)has the same meaning as in definition 5,
whereitiswrittenas((h,t,e),(h,r,f)).
Despite their superiority over NLC graph grammars, NCE graph
grammars do not cope either with the requirements of the tasks of the
domain of technical systems:
77
7 Classes, Complexity and Design Evaluation
1. The mechanism for context specification is weak, since a context
is restricted to incident edges of the target node–there is no way
to specify larger contexts. Furthermore, this type of context is
only taken into account within the embedding process, which
fact means that it cannot serve as an application condition.
2. Deletion is not easily performed, since the replacement graph has
to be non-empty.
7.1.2 The Gluing Approach
The gluing approach is an edge-centered concept that aims at the
replacement of hyperedges or hypergraphs by hypergraphs. Each hy-
peredge or hypergraph possesses a series of attachment nodes which
represent the interfaces to the outer world. Within a replacement step,
the item to be replaced is deleted from the host hypergraph with ex-
ception of the attachment nodes, which are at the same time external
nodes of the host hypergraph, and the new hypergraph is embedded
in its place by identifying its attachment nodes with the external nodes.
Thus, the embedding is performed by unifying nodes.
There exists a large set of hypergraph grammars following the glu-
ing approach. The most well-known family is called hyperedge replace-
ment (HR) grammar.
HR Grammars
In analogy to the connecting approach case, in which node-based
and graph-based grammars are distinguished, we differentiate be-
tween hyperedge-based and hypergraph-based hyperedge replace-
ment grammars. Hyperedge-based hyperedge replacement grammars
are defined as in [Drewes et al.,1997].
Definition 9 (Hyperedge Replacement Grammar)
A hyperedge replacement grammar is a tuple G =Σ,P,swhere
78
7.1 Classical and Design Graph Grammars
•Σis the set of terminal and nonterminal labels3,
•P is a finite set of hypergraph transformation rules or productions over
Σ, of which a production has the form T →R, where T is a hyperedge
label and R is the replacement hypergraph,
•and s ∈Σis the initial symbol.
Hyperedge replacement grammars are not powerful enough for
the design tasks envisioned. The following weaknesses hinder the use
of this concept:
•HR grammars are intrinsically context-free, since the item of the
left-hand side of a rule is completely deleted and replaced by
the hypergraph of the right-hand side. In order to introduce
matching-level context—a context that serves as an application
condition—into this concept, one would have to either extend
HR grammars or integrate the context into the target hyperedge
or hypergraph. This means that the context would have to be
deleted and restored by means of the replacement hypergraph.
•HR grammars are weaker than the confluent NCE graph gram-
mars of the connecting approach in terms of generative power
([Engelfriet and Rozenberg,1997], page 4).
7.1.3 Hybrid Approaches
Apart from design graph grammars there exist other hybrid ap-
proaches in the literature. In [Courcelle et al.,1993] the authors present
another hybrid graph grammar, the handle hypergraph grammar.This
hybrid graph grammar, as the name already implies, is based on the
hyperedge replacement approach and has some node replacement fea-
tures. A similar approach that has a simpler rewriting mechanism is
the HR grammar with eNCE rewriting,presentedin[Kim and Jeong,
3Only hyperedges are labeled in HR grammars.
79
7 Classes, Complexity and Design Evaluation
1996]. Another hybrid approach, the hypergraph NCE graph grammar,
is introduced in [Klempien-Hinrichs,1996]. This concept is based on
the node replacement approach. In the following we briefly describe
these approaches and address their usability for design purposes.
Handle Hypergraph Grammars
Handle hypergraph (HH) grammars rewrite handles. A handle is an
edge (or hyperedge) together with all of its nodes. Within a hyper-
graph transformation step a handle is deleted, including all incident
edges; the replacement hypergraph is then embedded into the host hy-
pergraph by means of embedding instructions based on the connecting
approach [Courcelle et al.,1993,Rozenberg,1997].
HH grammars have a simpler embedding mechanism than tradi-
tional node replacement graph grammars, since the deleted edges in-
cident to the handle do not have to be distinguished but only restored;
therefore, there is no edge relabeling. On the other hand, a handle is
the smallest item that can be replaced; this means that rules have to
match and delete at least one edge and two nodes (excluding incident
edges from the host hypergraph), whereas in the design graph gram-
mar approach the smallest item is a single node, which seems more
flexible. Since the domain of technical systems requires a node cen-
tered mechanism and due to the above disadvantages, we conclude
that this concept does not meet our requirements.
Hypergraph Replacement with eNCE Rewriting
Hypergraph replacement grammars with an eNCE way of rewriting
(HRNCE) are handle-rewriting grammars like the HH grammars de-
scribed above. HRNCE grammars possess a simple structure and are
as easy to use as NLC grammars, but are still powerful in terms of
expressiveness [Kim and Jeong,1996].
Again, the design tasks imposed by the domain of technical sys-
tems require a node centered concept, and, although HRNCE gram-
80
7.1 Classical and Design Graph Grammars
mars represent a powerful manipulation mechanism, they share the
same disadvantages with the HH grammars. Thus, HRNCE grammars
are not fitting for our purposes.
Hyperedge Neighborhood Controlled Embedding Graph
Grammars
Hyperedge NCE (hNCE) graph grammars generalize classical NCE
grammars by extending the traditional approach to handle hyperedges
instead of ordinary edges. The necessity for this enhanced NCE gram-
mar arises from the need to perform special hypergraph transforma-
tions, which cannot be expressed by hyperedge or handle rewriting in
hypergraphs or by node replacement in bipartite graphs, on Petri nets
[Klempien-Hinrichs,1996].
Basically, an hNCE grammar works exactly like an NCE gram-
mar: A nonterminal target node, together with all incident hyperedges,
is deleted. Then, the replacement hypergraph is embedded into the
host graph by adding hyperedges that are created in compliance with
the embedding instructions. hNCE grammars can generate the same
graph languages generated by HR grammars, and, according to the
author of [Klempien-Hinrichs,1996], hNCE grammars are assumed to
have at least the same generative power as S-HH grammars4.
hNCE grammars, although apparently versatile and powerful in
terms of expressiveness, only extend the NCE concept to hyperedges
and hypergraphs. This additional functionality is not required for the
tasks of the domain of technical systems, and only adds further over-
head, since the use of hyperedges and hypergraphs make the formula-
tion of graph transformation rules cumbersome. Thus, this concept is
not adequate for our needs.
4S-HH grammars are separated HH grammars, i. e., no two nonterminal hyperedges are
adjacent in the right-hand side of hypergraph transformation rules or in the initial
symbol or hypergraph.
81
7 Classes, Complexity and Design Evaluation
7.1.4 Design Graph Grammars
As seen in the previous sections, neither classical node replacement
graph grammars nor hyperedge replacement grammars seem to be
suitable for design tasks in the domain of technical systems; even the
powerful hybrid approaches proved to be inadequate for our needs.
Design graph grammars, on the other hand, encompass the benefits of
the connecting and gluing approaches, while remaining node replace-
ment based:
•Replacement paradigm. Concise formulation of node-based graph
transformation rules (NLC/NCE)
•Embedding. Access to individual nodes of the replacement graph
(NCE); unique embedding through attachment nodes(HR)
Furthermore, design graph grammars add some features of their
own:
•Matching. Fine grained control of matching
•Embedding.
–Extended replacement graph formulation
–Enhanced embedding instructions
–Flexible rule formulation by means of variable labels
•Context.
–Distinction between exact and partial contexts
–Context serves as an application condition
Figure 7.3 shows the relationship of design graph grammars to the
classical grammars with respect to their features.
In the following we present some formal results that establish the
relationship between design graph grammars and the classical graph
and hypergraph grammars.
82
7.1 Classical and Design Graph Grammars
NCE
HR
DGG
+ Context by context graph
+ Empty replacement graph
+ Links between cut nodes + Context by embedding rules
+ Connection by embedding
· Target graph
· Replacement graph
· Graph with labels
· Cut nodes
+ Context by target graph
+ Connection by gluing
+ Graph with hyperedges
Figure 7.3: Features of the different graph grammar concepts.
Theorem 1 (LNLC ⊆L
DGG)
Every NLC graph language generated by a node-based NLC graph gram-
mar can be generated by a node-based, context-free design graph grammar.
Proof.
Let an arbitrary NLC grammar G =Σ,P,I,sfor an NLC graph
language L be given. We construct a node-based, context-free DGG G=
Σ,P,sbased on G such that L(G)=L.
Obviously, s=sandΣ=Σ. The set of graph transformation rules Pis
defined as follows. Pcontains a graph transformation rule r:t→R,Ifor
each r ∈Pwithr:t→R. The embedding instruction set Iof each r∈P
contains the same embedding instructions as the set I. For each embedding
instruction i ∈Iwithi=(h,r)there is an embedding instruction i∈I
with i=((h,t,⊥),(h,v,⊥)),where
σ
R(v)=r. It is clear that L(G)=L.
Theorem 2 (LNCE ⊆L
DGG)
Every NCE graph language generated by a node-based NCE graph gram-
mar can be generated by a node-based, context-free design graph grammar.
83
7 Classes, Complexity and Design Evaluation
Proof.
Taking an arbitrary NCE grammar G=Σ,P,sfor an NCE graph lan-
guage L as a starting point, we construct a node-based, context-free DGG
G=Σ,P,swhose generated language L(G)=L.
Due to the strong similarity between both concepts, the construction is
straightforward. We set Σ=Σ,P
=Pands
=s. The graph transfor-
mation rules are identical in syntax and semantics for both concepts; only
the syntax of the embedding instructions differ: For each NCE embedding in-
struction i ∈Iwithi=(h,e/f,r)there is a DGG embedding instruction
i∈Iwith i=((h,t,e),(h,r,f)). Obviously, L(G)=L.
Theorem 3 (LHR ⊆L
DGG)
Every HR language generated by a hyperedge-based HR grammar can be
generated by a node-based, context-free design graph grammar, if hypergraphs
are interpreted as bipartite graphs.
Proof.
According to Engelfriet and Rozenberg ([Engelfriet and Rozenberg,
1990]and[Engelfriet and Rozenberg,1997], page 57ff.), LBnd−edNCE =LHR.
Hence, HR languages generated by HR grammars can be generated by non-
terminal neighbor deterministic boundary edNCE grammars, which in
turn can be simulated by DGGs, since LBnd−edNCE ⊆L
B−edNCE ⊆L
edNCE.
Thus, DGGs can generate HR languages and it follows that LHR ⊆L
DGG.
Figure 7.4 summarizes the above statements and illustrates the ex-
pressive power of design graph grammars.
7.2 Relationship to Programmed Graph Replacement Sys-
tems
Design graph grammars as proposed here shall enable domain experts
to formulate design expertise for various design tasks. Design graph
grammars result from the combination of different features of the clas-
sical graph grammar approaches, while special effort has been spent
to keep the underlying formalism as simple as possible.
84
7.2 Relationship to PGRS
DGG
Design graph
grammar HR
Hyperedge replacement
graph grammar, (bipartite)
NCE
Neighborhood-controlled
embeddding
Power wrt. languages
that can be generated
Figure 7.4: The expressive power of design graph grammmars.
When comparing design graph grammars to programmed graph
replacement systems (PGRS) one should keep in mind that the for-
mer is located at the conceptual level while the latter emphasizes the
tool character. PGRS are centered around a complex language allowing
for different programming approaches. PROGRES5,forinstance,of-
fers declarative and procedural elements [Schürr,1989,1991]fordata
flow oriented, object oriented, rule based and imperative program-
ming styles. A direct comparison between PROGRES to the concept
of design graph grammars is of restricted use only and must stay at
the level of abstract graph transformation mechanisms.
However, it is useful to relate the concepts of design graph gram-
mars to PGRS under the viewpoint of operationalization. PGRS are a
means—say: one possibility—to realize a design graph grammar by
5We chose PROGRES for illustration purposes only; other tools, such as PAGG (see
[Schürr,1997b] for a brief description and further pointers) or Fujaba [Nickel et al.,
2000], could have been used as well.
85
7 Classes, Complexity and Design Evaluation
reproducing its concepts. In this connection PROGRES fulfills the re-
quirements of design graph grammars for the most part. However,
PROGRES lacks the design graph grammar facilities for the formula-
tion of context, deletion operations, and matching control, which have
to be simulated by means of complex rules. Such a kind of emulation
may be useful as a prototypic implementation, but basically, it misses
a major concern of design graph grammars: Their intended compact-
ness, simplicity, and adaptivity with respect to a concrete domain or
task.
7.3 The Problem of Matching
Matching is a vital part of any rule-based concept. In order for a graph
transformation rule to fire it is necessary that a matching of the left-
hand side be found within the host graph. Additionally, the embed-
ding process requires that individual nodes be matched so that edges
can be drawn between them.
Matching is already a nontrivial issue in the context-free, graph-
based case, as implied by the subgraph matching problem described in
section 7.3.2. The inclusion of context adds to the complexity of match-
ing, because node-based matchings with context are then comparable
with graph-based matchings.
The specification of context as a means to restrict the application
of a graph transformation rule to a certain situation is an essential re-
quirement for design purposes. In the following the different types of
context are examined and the resulting consequences identified. Then,
the subgraph matching problem, a problem also related with context,
is described as well as a measure to diminish its effect. Finally, we
address the problem of context within backward execution of graph
transformation rules.
86
7.3 The Problem of Matching
7.3.1 Context and Its Consequences
As stated above, we differentiate between matchings with context
and without context. This leads to the following classification:
1. Node-based matching without context. This type of matching per-
tains to a single node and disregards its context completely.
Within a graph, a matching of a certain node takes at the most
linear time in the size of the graph.
2. Node-based matching with incident edges. This type of matching
yields a single node together with incident edges, which rep-
resent a very small and restrictedcontext.Thesearchforsuch
a node requires linear time in the size of the graph, if it can be
assumed that node degree is bounded by a constant, which is
usually the case.
3. Node-based matching with context graph. A matching of this type
includes a node and a nontrivial context, which size is only
bounded by the host graph itself. Thus, the most expensive
matching can be achieved in the node-based case.
4. Graph-based matching without context. Graph-based matchings
without context share the same worst-case complexity as the pre-
vious case. In average, though, one can expect this type of match-
ing to be of a larger scope, and therefore more expensive.
5. Graph-based matching with context graph. This type of matching
represents the most difficult case and shares the same worst-case
complexity as the previous matching type. However, since con-
text has to be matched as well, it is to be expected that this type
of matching behaves worse than the graph-based matching with-
out context in the average case.
For obvious reasons one should avoid formulating graph transfor-
mation rules more complex than case 2. However, in many cases, es-
pecially with respect to repair and optimization, graph transformation
rules with nontrivial matchings are required.
87
7 Classes, Complexity and Design Evaluation
7.3.2 The Subgraph Matching Problem
Subgraph matching6is a widely known NP-complete problem
[Garey and Johnson,1997,Köbler et al.,1993], and therefore no algo-
rithm implementing a solution to this problem will run in polynomial
time, assuming that NP =P.
In order to avoid this large effort one can make use of addi-
tional information to accelerate the subgraph matching step, whereas
the problem and its complexity remain unchanged. In [Bunke et al.,
1991a,b] the authors describe an efficient graph grammar implemen-
tation based on the Rete algorithm [Forgy,1982,Forgy and Shepard,
1987] that achieves considerable speedups in the best case. This same
approach could be adapted for our design graph grammar.
Example.
Let the following graph rules (actually only the left-hand
sides) be given7as in Figure 7.5.
AB
C
A ::= ...R1:
BA ::= ...R2:
CBA ::= ...R3:
CBA ::= ...R4:
12
3
Figure 7.5: Graph rule left-hand sides and a sample graph.
The corresponding Rete network including the activations is de-
picted by Figure 7.6.
Remarks.
The above example uses context-sensitive rules to illustrate
how the Rete network is compiled. Although the rules of our design
graph grammars are primarily context-free, this approach remains
6In the field of graph theory this problem is known as the subgraph isomorphism problem.
It should not be mistaken with the graph isomorphism problem, which lies in NP, but
for which it is still open if it is NP-complete [Garey and Johnson,1997,Arvind et al.,
1998,Köbler et al.,1993,Mehlhorn,1984].
7This example is a slightly modified version of the example found in [Bunke et al.,
1991a].
88
7.3 The Problem of Matching
A B C
Root
AB BC CA
ABC
ABC
R1 R2 R3 R4
(1)
(1,2) (3,1)(2,3)
(1,2), (2,3)
(1,2) (1,2), (2,3)
(1,2), (2,3),
(3,1)
(1,2), (2,3),
(3,1)
Figure 7.6: The compiled Rete network for the example of Figure 7.5.
fully applicable within the design analysis context, since graph rules
are to be executed in a backward fashion.
Remarks.
Figure 7.6 clearly shows that the Rete network is a compact
structure considering all partial and total matches. The ability to com-
bine partial matches to handle multiple rule activations is the decisive
factor here and accounts for the performance gain reached through the
use of this concept, which trades space for time.
7.3.3 Context within Backward Execution
As seen in section 4, the structural analysis of designs is done by
means of graph transformation rules executed in a backward fash-
89
7 Classes, Complexity and Design Evaluation
ion. A graph transformation rule T,C→R,Iis interpreted as
R,I→T,C, i. e., the replacement graph Rrepresents the new tar-
get graph, the target graph Trepresents the new replacement graph,
and the context graph Cspecifies the embedding explicitly. The em-
bedding instructions Iplay the role of the new context—this fact gives
rise to some issues that are addressed here.
Firstly, a context may be omitted, i. e., the graph transformation
rule is context-free. A backward execution of such a graph transforma-
tion rule leads to the question of how to deal with the embedding in-
structions: Either they are used solely for connection purposes and not
as a context specification (context-free backward execution), or they
are used for connection and context purposes (context-sensitive back-
ward execution).
Secondly, embedding instructions lack the exactness of a true con-
text graph, since they only represent rules that specify embeddings—if
there is no applicable situation, then an embedding instruction is ig-
nored. Thus, different “contexts” may be matched by the embedding
instructions.
7.4 Foundations of Derivations and Membership
This section is dedicated to the basic properties of design graph gram-
mars, which allow a classification of design graph grammars into dif-
ferent subclasses with certain properties. Furthermore, special restric-
tions that lead to interesting and promising results related to the mem-
bership problem are addressed.
7.4.1 Basic Properties
There are a series of basic properties of graph grammars that can
be examined, but the probably most important property is conflu-
ence. Confluence has far-reaching consequences, since many NP- or
PSPACE-complete problems related to graph grammars that have this
property can be solved in (nondeterministic) polynomial time, such as
90
7.4 Foundations of Derivations and Membership
the membership problem. However, before we proceed with the defi-
nition of confluence, we provide some other basic notions.
Lemma 1 (Associativity of Design Graph Grammars)
Let G=Σ,P,sbe a design graph grammar, with graph transformation
rules T1→R1,I1and T2→R2,I2, and let G a host graph. Moreover,
let R1contain a matching of T2.ThenG[T1|R1][T2|R2]=G[T1|R1[T2|R2]].
The following definition of the confluence property is based on
[Engelfriet and Rozenberg,1997].
Definition 10 (Confluence)
A context-free design graph grammar G=Σ,P,sis confluent,iffor
every pair of rules T1→R1,I1and T2→R2,I2with Ricontains
amatchingofT
i∈{1,2}, and for any arbitrary host graph H containing two
matchings of T1and T2, the following equality holds:
H[T1|R1][T2|R2]=H[T2|R2][T1|R1]
Put in other words, a design graph grammar is confluent if the sequence
of rule application is irrelevant with respect to the set of derivable graphs.
The following definition of confluence (based on the definition of
confluence for edNCE grammars in [Engelfriet and Rozenberg,1997])
is more detailed and makes an a-priori statement possible.
Definition 11 (Confluence 2)
A context-free design graph grammar G =Σ,P,sis confluent, if for all
graph transformation rules T1→R1,I1and T2→R2,I2in P, all nodes
x1∈VR1,x2∈VR2, and all edges labels
α
,
δ
∈Σ, the following equivalence
holds:
∃
β
∈Σ:((t2,t1,
α
),(t2,x1,
β
)) ∈I1and
((
σ
(x1),t2,
β
),(
σ
(x1),x2,
δ
)) ∈I2
⇔
91
7 Classes, Complexity and Design Evaluation
∃
γ
∈Σ:((t1,t2,
α
),(t1,x2,
γ
)) ∈I2and
((
σ
(x2),t1,
γ
),(
σ
(x2),x1,
δ
)) ∈I1
Remarks.
The above definition allows for an algorithmic confluence
test of context-free design graph grammars. Furthermore, confluence
can only be guaranteed for constructive transformations; thus, the
presence of destructive graph transformation rules makes a confluence
statement improbable.
Theorem 4 (Context-free Design Graph Grammars and Confluence)
Context-free design graph grammars are not inherently confluent.
Proof.
Let G =Σ,P,sbe a context-free design graph grammar and H =
{v},∅,{(v,t1)} a host graph. Let r1,r2∈P be two graph transformation
rules as follows:
r1:t
1→R1,I1with R1=∅and I1=∅
r2:t
1→R2,I2with R2={v1,v2},{{v1,v2}},{(v1,t1),(v2,t2)}
and I2=∅
With these two rules the following derivations are possible:
1. H ⇒r1H1=∅
2. H ⇒r2H2⇒r1H21 ={v2},∅,{(v2,t2)}
Since H1=H21,Gisnotconfluent.
7.4.2 Special Restrictions for Membership Test
As hinted previously, the confluence property leads to positive re-
sults and is therefore desirable. In this section two possible restrictions
to node-based design graph grammars are presented, each of which
implies confluence or even stronger properties. The following defini-
tions and results are based on [Engelfriet and Rozenberg,1997].
92
7.4 Foundations of Derivations and Membership
Leftmost Derivation
Leftmost derivations of design graph grammars are achieved by im-
posing a linear order on the nodes of the right-hand sides of the graph
rules—this is necessary since there is no natural linear order as in the
case of string grammars. This order induces a linear order on the nodes
of the sentential forms of the graph grammar.
Definition 12 (Ordered Graph, Ordered Design Graph Grammar)
AgraphG=VG,EG,
σ
Gis an ordered graph, if there is a linear order
(v1,...,vn)with vi∈VGfor 1≤i≤nand|VG|=n.
A design graph grammar G=Σ,P,sis ordered, if for each rule t →
R,Iin P the replacement graph R is ordered.
Let Gbe an ordered design graph grammar containing a graph
transformation rule t→R,I. When embedding the replacement
graph Rwith the linear order (w1,...,wR)into a host graph Gwith lin-
ear order (v1,...,vi−1,t,vi+1,...,vG), the order of the resulting graph
Gis constructed as follows: (v1,...,vi−1,w1,...,wR,vi+1,...,vG).
Definition 13 (Leftmost Derivation)
Let Gbe an ordered design graph grammar. For an ordered graph G, a
derivation step G ⇒v,pGof Gis a leftmost derivation step if v is the first
nonterminal node in the order of G(p represents here the graph transforma-
tion rule used). A derivation is leftmost if all its steps are leftmost.
The graph language leftmost generated by G is denoted by Llm(G).
Remarks.
The ordering of the sentential forms has no influence on the
language L(G)generated by a graph grammar G.
Lemma 2 (Expressiveness of Leftmost Generated Languages)
Let Gbe an ordered design graph grammar. Then Llm(G)does not depend
on the sequence of rule applications.
93
7 Classes, Complexity and Design Evaluation
Proof: See [Engelfriet and Rozenberg,1997], page 40, where the authors
show that the restriction to leftmost derivations is equivalent to the restric-
tion to confluent grammars. This same argumentation holds for design graph
grammars.
Theorem 5 (Characterization of Leftmost Generated Languages)
The class of languages leftmost generated by design graph grammars is
equal to the class of languages generated by confluent design graph grammars.
Proof: See [Engelfriet and Rozenberg,1997], page 41ff, where a proof for
confluent NCE grammars is given. Due to the strong similarity between de-
sign graph grammars and NCE grammars, the proof for design graph gram-
mars is analogous.
Boundary Restriction
Since design graph grammars are NCE graph grammars, various
properties valid for NCE grammars also hold for design graph gram-
mars. However, important properties such as confluence, decidability
of the membership problem etc. do not necessarily hold for the whole
class. For certain subclasses, on the other hand, it can be shown that
these properties hold. In the following we introduce one such class,
whose definition stems from [Engelfriet and Rozenberg,1997].
Definition 14 (Boundary Design Graph Grammar)
A design graph grammar G =Σ,P,swith directed edges and edge
labels is boundary, or a boundary design graph grammar, if, for every pro-
duction T →R,I,
(B1) R does not contain adjacent nonterminal nodes, and
(B2) The set I does not contain any embedding instructions of the form
((
σ
,t,
β
),(
σ
,x,
γ
)) where
σ
is nonterminal.
94
7.4 Foundations of Derivations and Membership
In [Engelfriet and Rozenberg,1997] it is also shown that only one of the
conditions (B1) or (B2) is actually necessary, since each condition implies the
other one.
Design graph grammars are not boundary by definition, since both
(B1) and (B2) do not hold. However, design graph grammars can be
easily restricted to have this property.
Consequences of the Restrictions
In the last two sections we introduced two possible—but inherently
different—restrictions to design graph grammars that are easy to per-
form. The application of these restrictions has a series of interesting
consequences [Engelfriet and Rozenberg,1997]:
•Confluent design graph grammars are associative.
•The membership problem for confluent design graph grammars
is in NPTIME ([Engelfriet and Rozenberg,1997], page 82).
•The membership problem for boundary design graph grammars
is in PTIME, if, due to labeling restrictions, the subgraph match-
ing problem can be solved in polynomial time ([Slisenko,1982,
Rozenberg and Welzl,1986,Schuster,1987]).
Boundary Design Graph Grammars
In order to make design graph grammars boundary, additional termi-
nal nodes called junctions (also called “T-connections”) are introduced.
The nodes are inserted into rules having more than one nonterminal
on the right-hand side. As an example, we apply this restriction to the
design graph rules of section 5.2, of which only rule (R4) is actually
changed, as depicted by Figure 7.7.
95
7 Classes, Complexity and Design Evaluation
p
?
sliquid
ssolid
sliquid ?
?p
sliquid
sliquid
ssolid
p
?
sliquid
ssolid
sliquid
?p
sliquid
?
sliquid
ssolid
Figure 7.7: Change of rule (R4) resulting from the boundary restric-
tion.
Remarks.
Note that this restriction of design graph grammars does
not hinder its use for our purposes. In fact, the additional nodes (and
edges) resulting from the boundary restriction can be easily removed
by means of a post-processing routine, as far as a removal is possible.
Since this post-processing step only consists of removing additional
nodes of degree 2, the required effort amounts to linear time in the
size of the graph. Thus, the complete process remains polynomial.
7.5 Membership and Derivation in Design
This section is dedicated to the problems of membership and deriva-
tion as applied to design tasks. In particular, the membership problem
is examined and statements about its complexity made, whereas spe-
cial attention is given to the polynomial case and the graph class re-
strictions needed to make this possible. Furthermore, the problems of
shortest derivations and distance between graphs, which are closely
related to the synthesis task, are addressed.
96
7.5 Membership and Derivation in Design
7.5.1 The Membership Problem for Graph Languages
To solve the membership problem for graph languages a method is
required with which a graph can be parsed and a derivation tree based
on the design graph grammar can be constructed. It suffices, however,
to know that the given graph was generated from the initial symbol
of the design graph grammar, i. e., a derivation tree is not absolutely
necessary.
In the area of string languages there are some algorithms that were
devised to solve exactly the same problem. One of these is the Cocke-
Younger-Kasami algorithm (CYK algorithm) described in [Hopcroft,
1979]. The basic idea is to start from the given sentential form and ap-
ply the grammar productions backwards, taking all possible combina-
tions in consideration. If the word belongs to the language generated
by the string grammar, then the initial symbol will be derived. The
CYK algorithm is a dynamic programming procedure taking O(n3)
time in the length of the input word. In order to guarantee this run-
time complexity, the grammar must be in Chomsky normal form, i. e.,
rules may only have either one terminal or two nonterminal symbols
on the right-hand side.
Example.
In the following we illustrate how the CYK algorithm works.
For this purpose, let the following simple string grammar in Chomsky
normal form be given:
S→C11X|C12X
C11 →T1X
C12 →T1X
T1→C21X|C22X
C21 →T2X
C22 →T2X
T2→t
X→x
97
7 Classes, Complexity and Design Evaluation
Figure 7.8 shows how the CYK algorithm works on the input txxxx;
Figure 7.9 shows a parse tree for the word txxxx. Note that the parsing
tree is a binary tree (due to the Chomsky normal form), and that the
table generated by the CYK algorithm has the same structure.
1
2
3
4
5S
T2
T1
C11, C12
C21, C22
t
X
x
X
x
X
x
X
x
Ø
Ø
Ø
ØØ
Ø
Figure 7.8: Recognition of the word txxxx by the CYK algorithm.
S
T2
T1
C21
C11
tx
X
xxx
X
X
X
Figure 7.9: A parse tree derived by the CYK algorithm for the word
txxxx.
98
7.5 Membership and Derivation in Design
In contrast to graph grammars, string grammars possess a linear
ordering that specifies the context—or relevant neighborhood—of a
symbol, namely the symbols located to the left and right. The CYK
algorithm (and most parsing algorithm for string languages) makes
use of this trivial property, as well as of the normal form used for the
string grammar, as can be seen in Figures 7.8 and 7.9, and of the in-
trinsic freedom of rule application order. Graphs, unlike string words,
do not have this linear ordering property, which fact makes the search
for a rule with matching right-hand side a toilsome job due to the sub-
graph matching problem (see section 7.3.2 for further details). Figure
7.10 shows a graph and a string graph together with their relevant con-
texts.
v
s
Figure 7.10: Relevant contexts in graphs and strings.
Indeed, in [Brandenburg,1983] it is shown that the membership
problem is NP- or PSPACE-complete for a variety of graph languages,
including restricted context-free languages such as the ones generated
by NLC grammars, which are a special case of NCE grammars8.Fur-
thermore, it is argued in [Brandenburg,1983] that the finite Church
Rosser property9is of crucial importance for the existence of a poly-
nomial time recognition algorithm.
8NLC graph grammars do not have edge directions or labels. See section 7.1 or
[Engelfriet and Rozenberg,1997] for details on NLC and NCE grammars.
9This property states that nonoverlapping rewriting steps can be performed in any
order. This property is also known as confluence.
99
7 Classes, Complexity and Design Evaluation
7.5.2 Solving the Membership Problem in Polynomial Time
As seen in the previous section, the membership problem for graph
languages imposes exponential time complexity on any algorithm at-
tempting to solve it. This statement applies to the general case of arbi-
trary graph languages, which is far more than is required for our pur-
poses. Indeed, by restricting the graph language class under consider-
ation and using additional information, polynomial time complexity
can be achieved.
In the literature one can find some approaches that solve the mem-
bership problem in polynomial time, two of which are precendence
graph grammars [Kaul,1986]androoted context-free flowgraph languages
[Lichtblau,1991]. In the following we give a brief description of these
two approaches and reflect on the consequences for our problem.
Rooted Context-Free Flowgraph Languages
Flowgraph languages are context-free graph languages that supply a
suitable mechanism to represent the control flow of source programs10;
they have a strong resemblance to series-parallel graphs, to which the
graphs generated by our design graph grammars for the domain of
chemical engineering are also similar.
Rooted flowgraphs are graphs containing nodes (roots) that are
connected to all other nodes by means of paths. They are of vital
importance for the polynomial time recognition algorithm, since the
nodes have to be ordered somehow and these roots provide the ideal
starting points.
In order to test if a given graph belongs to the language of rooted
context-free flowgraphs, the given graph and the flowgraph grammar
have to be ordered. This is done by imposing ordered spanning trees
on the graph as well as on the graph grammar. This spanning tree is
then used to guide the reduction process, which acts in accordance
10The information and results presented in this section stem primarily from [Lichtblau,
1991].
100
7.5 Membership and Derivation in Design
with the given order. The recognition algorithm based on these prereq-
uisites requires polynomial time in the size of the input graph—further
details can be found in [Lichtblau,1991]and[Lichtblau,1990].
Whether a similar algorithm for the membership problem for non-
rooted flowgraph grammars exists still remains an open problem
[Lichtblau,1991].
Precedence Graph Grammars
Precedence graph grammars are context-free graph grammars that
have been enriched with precedence relations11. In the general case, the
membership problem is PSPACE-complete; however, if certain condi-
tions are met, the membership problem is decidable in O(n2)time,
where nis the number of nodes of the input graph.
In the field of string languages, only fast parsing algorithms taking
linear time in the length of the input have become widespread. There,
linear complexity can be attained by means of the introduction of ad-
ditional precedence relations, the requirement of the LL(k) or LR(k)
property [Hopcroft,1979] etc. Apart from the use of precedence re-
lations, all other approaches rely on the linear order of strings—the
efficiency of LR(k) methods, for example, is based on the fact that the
set of all valid prefixes can be formulated as a regular language. Prece-
dence relations, on the other hand, allow for processing in any order
or even in parallel.
Precedence graph grammars are conventional graph grammars
with additional precedence information. Every pair of adjacent sym-
bols is assigned a precedence determining which symbol is to be pro-
cessed first. Precedences always refer to a node pair (v,w),andeach
precedence may be of one of the following types:
1. Node vis to be processed before node w.
2. Node vis to be processed after node w.
11The information and results presented in this section stem primarily from [Kaul,1986].
101
7 Classes, Complexity and Design Evaluation
3. Nodes vand ware to be processed simultaneously.
4. Nodes vand wcan be processed in any order.
In order to achieve the time complexity of O(n2)claimed above,
the following conditions must hold:
•The graph grammar is confluent. Confluence is essential here, since
there are cases where the order of reduction steps is arbitrary
or not specified. If the graph grammar is not confluent, then the
reduction process may not be able to reach the initial symbol,
although it is derivable.
•The precedence relations are disjoint. This feature ensures that every
node pair is assigned a unique precedence relation, thus prevent-
ing any ambiguity in the reduction process.
•The graph productions are uniquely revertible. This requirement
arises from the fact that every reduction step, i. e., backward ex-
ecution of a rule, must be deterministic and achievable without
backups. Again, ambiguity is to be avoided.
In [Kaul,1986], precedence graph grammars do not have edge la-
bels in the usual sense; the precedences are edge attributes. The edge
label alphabet of design graph grammars can be enhanced to include
“precedence labels”, increasing the size of the edge label alphabet by a
factor of at most four12.
Remarks.
Please note that the precedence graph grammar approach is
not only applicable for special context-free graph classes such as out-
erplanar or series-parallel graphs, but for any context-free graph lan-
guage for which a precedence graph grammar with the above proper-
ties can be given.
For more details concerning precedence graph grammars, refer to
[Kaul,1986]and[Kaul,1987], where practical applications for prece-
dence graph grammars are presented.
12Actually, every edge label should only be assigned one precendence, therefore only
making the existing labels longer and not increasing their number at all.
102
7.5 Membership and Derivation in Design
Remarks.
The approaches presented above require additional infor-
mation or mechanisms in order to reach polynomial time complexity.
Thus, design graph grammars have to be extended to encompass and
make use of these approaches. As mentioned above, this can be done
by adding special symbols to the edge label alphabet or by imposing
some order on the nodes of the graph to be tested and on the nodes of
the graph grammar rules.
In section 7.4.2 we present some theoretical results found in the lit-
erature, among which is the statement that the membership problem
for boundary NCE grammars is in PTIME. This result is, as stated ear-
lier, theoretical in nature and does supply neither any concrete parsing
or recognition algorithm nor any statement regarding a precise time
complexity.
7.5.3 Shortest Derivation
The length of a derivation is an adequate measure for the runtime
complexity of the generation of a design, which is the primary task of
the synthesis process described in section 5. Depending on the design
graph grammar used and on the order of graph transformation rules
applied, a derivation will take at least linear time with respect to the
size of the graph, assuming that each rule application will generate
a finite number of terminal nodes only; on the other hand, the worst
case runtime complexity for a derivation is unbounded if cyclic partial
derivations exist and destructive graph transformation rules are ap-
plied. Thus, only a statement concerning the lower bound for the time
required for the derivation process is possible, i. e., a prediction can
only be ventured for the shortest derivation.
The design graph grammar concept, as presented in section 3,
does not impose any restriction upon the transformational behavior of
rules. In fact, the example of section 5.2 contains three different types
of rules: rules that fire only once, e. g. R1, rules that fire linearly in the
numberofinputs,e.g.R4, and rules that can fire arbitrarily often, e.
g. R6. The existence of the last rule type implies that the graph rule
system may not terminate. In fact, within a concrete technical domain
103
7 Classes, Complexity and Design Evaluation
such as the domain of chemical engineering one can distinguish be-
tween the following types of rules:
•Chain rules. Rules may only produce a single output, and rules
may not split nonterminal nodes into further nonterminal nodes,
such as in rule R4.Furthermore,weforbid cycles within the gen-
erated design, thus avoiding the repeated execution of rule se-
quences.
Due to these restrictions, the size of chemical plant designs gen-
erated by these rules is linearly related to the number of inputs
available. Therefore, the computational effort—in terms of the
number of rules applied—to produce a feasible design using
rules of this type is of the order O(n).
•Splitting rules. Now we drop the splitting restriction on rules, i.
e., splitting rules such as R4 are allowed. Depending on the num-
ber of inputs, further nonterminal nodes may be produced. This
results in O(n2)rule applications.
•Unrestricted rules. Lastly, rules that multiply the number of out-
puts are also allowed. Since with these rules arbitrarily many
new “inputs” can be generated, the computational effort is un-
bounded.
Accordingly, the overall complexity is unbounded, if all rule types
are allowed. However, the design graph grammar for chemical plants
presented in section 5.1 does not contain rules of the last type, thereby
limiting the overall computational effort for the generation of one
chemical plant design to O(n2)rule applications.
The termination drawback mentioned above can be avoided by for-
biddingtherepeateduseofthesamerulewithinthesamecontext—in
fact, graph grammar implementations do include facilities to specify
forbidden and allowed rules (see programmed graph replacement systems
in [Schürr,1997b]).
As hinted above, the presence of cycles containing destructive
transformations within a derivation may lead to an unbounded com-
plexity. However, by means of restrictions on the rule structures that
104
7.5 Membership and Derivation in Design
prevent such cycles, one may avoid this drawback. Before we address
this issue we shall introduce some necessary notions.
Definition 15 (Derivation)
A derivation is a sequence of graphs
π
=(G1,...,Gn)forwhichthesim-
ple derivation Gi⇒Gi+1,i∈{1,...,n−1},has been achieved by applying
a graph transformation rule.
π
Gdenotes a derivation based on graph transfor-
mation rules of a design graph grammar G=Σ,P,s,and
π
G(G)denotes a
derivation (s,...,G).
The shortest derivation is denoted by
π
∗.
Remarks.
A derivation
π
=(G1,...,Gn)may also be written as G1⇒∗
Gn. Although the latter form is widely used, we choose to use the first
form for convenience, since statements such as “G∈(G1,...,Gn)”are
more intuitive than “G∈G1⇒∗Gn”.
Definition 16 (Derivation Rule Sequence)
Let
π
=(G1,...,Gn)be a derivation. We define the derivation rule se-
quence belonging to
π
as
ρ
π
=(r1,...,rn−1),whereG
i⇒Gi+1by means
of a graph transformation rule ri,1≤i≤n−1.
Typically, the human understanding of the design of technical sys-
tems imposes a monotonic behavior on the design of a system. This
meansthatthedesignprocessisconstructive, deletion operations are
avoided where possible, leading to a system with the smallest num-
ber of steps possible. The following definitions shed some light on this
matter.
Definition 17 (Deletion Operation)
A deletion operation is a graph transformation step G ⇒Gsuch that
•|VT|>|VR|or
•|ET|>|ER|.
105
7 Classes, Complexity and Design Evaluation
Remarks.
Definition 17 implies that constructive graph transformation
steps may perform partial deletions, as long as there are more inser-
tions.
Figure 7.11 illustrates the consequence of the presence of deletion
operations within a derivation.
GGA
Constructive derivation
Destructive
derivation ...
?
Figure 7.11: A derivation containing deletion operations. Due to the
cycle the derivation length is unbounded..
With the aid of the above notions the aforementioned restriction to
rule structures, which represents a special property, can be introduced
formally.
Definition 18 (Monotonicity, Shortcut-Freedom)
Let G,Gbe graphs and Ga design graph grammar. A derivation
π
=
(G,...,G)is called monotonic, if and only if
ρ
π
does not involve deletion
operations.
Gis monotonic, if and only if for every G ∈L(G)there exists a monotonic
derivation
π
G(G).
Gis called shortcut-free, if for every G ∈L(G)the shortest derivation is
a monotonic derivation.
Remarks.
Shortcut-freedom means that there is no shortest derivation
containing deletion operations.
Figure 7.12 shows a monotonic derivation.
106
7.5 Membership and Derivation in Design
??
?
?
Figure 7.12: A monotonic derivation of a chemical plant.
7.5.4 Distance between Graphs
Another issue that is closely related to the shortest derivation prob-
lem addressed in the previous section is the distance between graphs.
But, instead of providing some means to predict the effort necessary to
generate a design fulfilling the given constraints, the focus now lies in
supplying a statement concerning the quality of the design.
The quality of a design Gis measured by the distance from Dto
the ideal design G∗, as provided by an expert. In practice, this is done
by determining the necessary graph transformation steps required for
the derivation (G,...,G∗)and calculating the involved effort.
Since our approach is bound to a concrete design graph grammar
within a given domain, we have to determine the distance between
a design Gand the ideal design G∗by means of the graph transfor-
mations supplied by the design graph grammar. Hereby we assume
that the ideal design G∗is also derivable with the given design graph
grammar. Hence, we distinguish between the direct distance between
twographsaswellasthederivational distance between two graphs.
Figure 7.13 depicts both situations.
Talking about Figure 7.13, it is clear that the derivational distance
between the two designs is equivalent to the effort necessary for the
“derivation” (G,...,GA,...,G∗). Put in other words, the distance be-
tween Gand G∗is given by the effort required to transform Gback
107
7 Classes, Complexity and Design Evaluation
Common
ancestor GA
G*
G
Derivation A1
Derivation A2
Direct
transformation
Derivational
transformation
?
Figure 7.13: Distance between a design Gand the ideal design G∗with
respect to the design graph grammar derivation.
into an ancestor GAand the effort required to derive G∗from this com-
mon ancestor GA(in the following let GAdenote an ancestor setential
form).
Remarks.
In some favorable cases it may happen that a design Gis an
ancestor of the ideal design G∗.
Determining the Graph Transformation Sequence
The effort required to solve the task of determining the graph transfor-
mation sequence necessary for the derivation (G,...,G∗)depends on
two factors: the degree of information given and the desired granular-
ity of the distance statement.
In order to determine the derivational distance between a design G
and the ideal design G∗one needs the derivations belonging to these
two graphs. Four different cases can be distinguished, representing the
degree of information supplied:
1. Derivations of Gand G∗are unknown.
108
7.5 Membership and Derivation in Design
2. Derivation of Gis unknown, derivation of G∗is known.
3. Derivation of Gis known, derivation of G∗is unknown.
4. Derivations of Gand G∗are known.
The first two cases can be ruled out, since the design Ghas been au-
tomatically generated—its derivation is therefore known. Thus, only
the last two cases remain as possible starting points. A derivation of
G∗, if not available, can be determined by means of the methodology
presented in section 4.
As far as the desired granularity of the distance statement is con-
cerned, one has to decide how much effort to invest in calculating the
derivational distance described above. On the one hand, a naive ap-
proach consisting of a simple comparison of derivations is conceivable.
This approach implies comparing
π
(G)and
π
(G∗)element-wise, i. e.,
searching for a graph GAwith GA∈
π
(G)and GA∈
π
(G∗).Thisap-
proach leads to a gross upper bound for the derivational distance be-
tween Gand G∗. On the other hand, a more elaborate approach involv-
ing finding the “greatest” common ancestor results in a lower upper
bound for the derivational distance.
The search for a common ancestor is a nontrivial task involving
solving the subgraph matching problem mentioned in section 7.3.2.
The search for the “greatest” common ancestor is even more toilsome,
since there may exist more than one derivation for a given graph. This
means that the comparison of alternative derivations may be neces-
sary. Please note that this problem does not correspond to the NP-
hard maximal common subgraph problem [Koch,2001], although the al-
gorithms described there could be used to find a maximal common
subgraph, which in turn represents at least an approximation of the
greatest common ancestor.
Again, the monotonicity property proves to be a valuable feature
of a design graph grammar because it makes the search for a common
ancestor much easier. In fact, the absence of deletion operations re-
duces the search space considerably, since monotonicity implies there
is an upper bound for the derivation length, whereas with deletion
109
7 Classes, Complexity and Design Evaluation
operations a derivation may be arbitrarily long. Thus, some way to
determine if a design graph grammar is monotonic is mandatory.
Lemma 3 (Monotonicity Requirements)
Let a design graph grammar G=Σ,P,sbe given. Gis monotonic, if
the following holds for every graph transformation rule r =T,C→R,I
of P: R encompasses a matching of T.
Put in other words, the target graph is a subgraph of the replacement
graph.
Determining the Effort of the Transformation
After determining the graph transformation rules required for the
derivation G⇒∗G∗, the effort necessary for this transformation can
be calculated from both the domain and the graph-theoretical point of
view.
In order to take the domain into account, we introduce a function
cdom :P→R+
0that yields for a graph grammar G=Σ,P,sthe effort
for the application of a given rule r∈Pwithin the domain dom.Now,
the overall domain effort when transforming a design according to a
derivation
π
can be computed as follows:
effort(
π
)= ∑
r∈
ρ
π
cdom(r)
If a function cdom cannot be stated, a function cgg :P→R+
0that
computes the graph-theoretical effort, which includes aspects such as
context and matching, must be used instead:
effort(
π
)= ∑
r∈
ρ
π
cgg(r)
110
8 Summary
The goal pursued by this thesis was the improvement of design au-
tomation for technical systems. As argued in chapter 1, the design pro-
cess encompasses various tasks at different granularity levels, which
cannot all be tackled efficiently with present-day technology. Thus,
abstractions belonging to model simplification have to be applied in
order to make the solution process of a design problem more pliable.
At this simplified level a holisitic support of the design procedure is
possible. For this purpose we introduced the concept of design graph
grammars, which, at the level of parameterized building blocks, allow
for the structural manipulation of graphs representing technical sys-
tems.
Through simplification and by means of design graph grammars,
the tasks associated with a design problem—structure generation, be-
havioral model synthesis, structural and behavioral analysis, design
evaluation, design repair and design optimization—become tractable.
The concepts introduced are uniformly applicable throughout the de-
sign cycle and allow for automation in areas that have been as yet
left untouched by traditional approaches, of which structural synthesis
and analysis benefitted the most.
The domain of chemical engineering, among others, provided dif-
ferent design tasks that we used to exemplify and, by means of
DIMod—a prototypical design tool, validate our approach. A chem-
ical process is modeled as a graph whose nodes describe the build-
ing blocks, or unit-operations, and whose edges specify the proper-
ties of the processed substance at a simplified level. Modifications of
a chemical process are defined as node-insertion and node-deletion
111
8 Summary
operations, which in turn are formalized by means of design graph
grammars.
Thus, design solutions for a chemical processing problem can be
produced and verified automatically by applying graph production
rules that encode an engineer’s design knowledge. However, draw-
backs to this approach do exist: design generation has a theoretically
unbounded runtime behavior, and the verification of a design solution
does not work for arbitrary structures—they must comply with the
encoded design knowledge and the structural restrictions imposed by
the design graph grammar model. Given a properly encoding of the
design knowledge, a large set of feasible designs can be generated or
verified at an acceptable computational effort.
Furthermore, efficient methods to improve the search process con-
nected to design generation were presented in chapter 5.Thesetech-
niques are connected to different aspects of the search process and
may, therefore, be combined; however, the applicability of one of the
presented techniques depends strongly on the knowledge representa-
tion implied by the domain.
All in all, our approach provides insights and evaluation of the
methodologies necessary for an entire automation of the design pro-
cess of technical systems. In particular, the use of model simplification
and structural manipulation by design graph grammars proves to be
advantageous within this context.
112
Bibliography
V. Arvind, R. Beigel, and A. Lozano. The Complexity of Modular
Graph Automorphism. In Proc. 15th Annual Symp. on Theoretical As-
pects of Computer Science, volume 1373 of LNCS, pages 172–182, 1998.
F. Brandenburg. On the Complexity of the Membership Problem of
Graph Grammars. In M. Nagl and J. Perl, editors, Graphtheoretic Con-
cepts in Computer Science, pages 40–49, Linz, 1983. Trauner Verlag.
F. Brandenburg. Designing Graph Drawings by Layout Graph Gram-
mars. In R. Tamassia and I. G. Tollis, editors, Proc. DIMACS Int.
Work. Graph Drawing, GD, number 894 in Lecture Notes in Computer
Science, LNCS, pages 416–427, Berlin, Germany, 1994. Springer-
Verlag.
A. Brinkop and N. Laudwein. Konfigurieren von industriellen Rühr-
werken. KI, 2:54–59, 1993.
H. Bunke, T. Glauser, and T.-H. Tran. An Efficient Implementation
of Graph Grammars based on the RETE Matching Algorithm. In
H. Ehrig, H.-J. Kreowski, and G. Rozenberg, editors, Proc.4th.Int.
Workshop on Graph Grammars and their Application to Computer Sci-
ence, volume 532 of Lecture Notes in Computer Science, pages 174–189.
Springer-Verlag, 1991a.
H. Bunke, T. Glauser, and T.-H. Tran. Efficient Matching of Dynami-
cally Changing Graphs. In Selected Papers from 7th Scandinavian Conf.
Theory and Applications of Image Analysis, pages 110–124. World Sci-
entific, 1991b.
113
Bibliography
B. Courcelle, J. Engelfriet, and G. Rozenberg. Handle-rewriting Hy-
pergraph Grammars. Journal of Computer and System Sciences, 46:
218–270, 1993.
F. Drewes, H.-J. Kreowski, and A. Habel. Hyperedge Replacement
Graph Grammars. In G. Rozenberg, editor, Handbook of Graph Gram-
mars and Computing by Graph Transformation, pages 95–162. World
Scientific, Singapore, 1997.
H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors. Hand-
book of Graph Grammars and Computing by Graph Transformation,vol-
ume 2 Applications, Languages and Tools. World Scientific, 1999a.
H. Ehrig, H.-J. Kreowski, U. Montanari, and G. Rozenberg, editors.
Handbook of Graph Grammars and Computing by Graph Transformation,
volume 3 Concurrency, Parallelism and Distribution. World Scien-
tific, 1999b.
J. Engelfriet and G. Rozenberg. A Comparison of Boundary Graph
Grammars and Context-Free Hypergraph Grammars. Inform. and
Comput., 84:163–206, 1990.
J. Engelfriet and G. Rozenberg. Node Replacement Graph Grammars.
In G. Rozenberg, editor, Handbook of Graph Grammars and Comput-
ing by Graph Transformation, pages 1–94. World Scientific, Singapore,
1997.
A. Fettweis. Wave Digital Filters: Theory and Practice. Proceedings of
the IEEE, 74(2):270–327, Feb. 1986.
C. L. Forgy. Rete: A Fast Algorithm for the Many Pattern / Many
Object Pattern Match Problem. Artificial Intelligence, 19:17–37, 1982.
C. L. Forgy and S. J. Shepard. Rete: A Fast Match Algorithm. AI Expert,
2(1):34–40, Jan. 1987.
F. Frantz. A Taxonomy of Model Abstraction Techniques. In Proceed-
ings of the 1995 Winter Simulation Conference (WSC 95), Proceedings
in Artificial Intelligence, pages 1413–1420, Arlington, VA, Dec. 1995.
114
Bibliography
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to
the Theory of NP-Completeness. W. H. Freeman and Company, New
York, 1997.
J. S. Gero. Design Prototypes: A Knowledge Representation Scheme
for Design. AI Magazine, 11:26–36, 1990.
W. Götte. Ein Wissensbasiertes System zur Konfigurierung von Rohrbün-
delwärmeüberträgern. VDI-Verlag, 1995.
W. Götte and H. Schmidt-Traub. Wissensbasierte Planungsmethoden
zur Konfigurierung von Rohrbündelwärmeüberträgern. Chemie In-
genieur Technik, 11:1455–1459, 1996.
J. E. Hopcroft. Introduction to Automata Theory, Languages and Computa-
tion. Addison-Wesley, 1979.
D. Jungnickel. Graphs, Networks and Algorithms, volume 5 of Algorithms
and Computation in Mathematics. Springer, 1999.
M. Kaul. Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken.
PhD thesis, Fakultät für Mathematik und Informatik, Universität
Passau, Passau, Germany, 1986.
M. Kaul. Practical Applications of Precedence Graph Grammars. In
H. Ehrig, M. Nagl, G. Rozenberg, and A. Rosenfeld, editors, Graph
Grammars and Their Application to Computer Science, number 291 in
Lecture Notes in Computer Science, pages 326–342, Berlin, 1987.
Springer-Verlag.
C. Kim and T. Jeong. HRNCE Grammars – A Hypergraph Generating
System with an eNCE Way of Rewriting. In J. Cuny, H. Ehrig, G. En-
gels, and G. Rozenberg, editors, Graph Grammars and Their Applica-
tion to Computer Science, number 1073 in Lecture Notes in Computer
Science, pages 383–396, Berlin, 1996. Springer-Verlag.
R. Klempien-Hinrichs. Node Replacement in Hypergraphs: Simu-
lation of Hyperedge Replacement and Decidability of Confluence.
In J. Cuny, H. Ehrig, G. Engels, and G. Rozenberg, editors, Graph
Grammars and Their Application to Computer Science, number 1073
115
Bibliography
in Lecture Notes in Computer Science, pages 397–411, Berlin, 1996.
Springer-Verlag.
A. Knoch and M. Bottlinger. Expertensysteme in der Verfahrenstech-
nik – Konfiguration von Rührapparaten. Chem.-Ing.-Tech., 65(7):802–
809, 1993.
J. Köbler, U. Schöning, and J. Torán. The Graph Isomorphism Problem: Its
Structural Complexity. Birkhäuser, 1993.
I. Koch. Enumerating All Connected Maximal Common Subgraphs in
Two Graphs. Theoretical Computer Science, 250(1–2):1–30, 2001.
M. Korff. Application of Graph Grammars to Rule-based Systems. In
H. Ehrig, editor, Graph Grammars and Their Application to Computer
Science, number 532 in Lecture Notes in Computer Science, pages
505–519, Berlin, 1991. Springer-Verlag.
U. Lichtblau. Flußgrapggrammatiken. PhD thesis, Universität Olden-
burg, Oldenburg, Germany, 1990.
U. Lichtblau. Recognizing Rooted Context-Free Flowgraph Languages
in Polynomial Time. In H. Ehrig, editor, Graph Grammars and Their
Application to Computer Science, number 532 in Lecture Notes in
Computer Science, pages 538–548, Berlin, Germany, 1991. Springer-
Verlag.
W. Marquardt. Rechnergestützte Erstellung verfahrenstechnischer
Prozeßmodelle. Chem.-Ing.-Tech., 64(1):25–40, 1992.
W. Marquardt. Trends in Computer-Aided Process Modeling. Comput-
ers chem. Engng., 20(6/7):591–609, 1996.
K. Mehlhorn. Data Structures and Algorithms, volume 2 Graph Algo-
rithms and NP-Completeness. Springer, Berlin, 1984.
U. Nickel, J. Niere, and A. Zündorf. Tool demonstration: The Fujaba
Environment. In Proc. 22nd Intl. Conference on Software Engineering,
pages 742–745. ACM Press, 2000.
116
Bibliography
C. C. Pantelides. Speedup – Recent Advances in Process Simulation.
Comput. chem. Engng., 12(7):745–755, 1988.
P. C. Piela, T. G. Epperly, K. M. Westerberg, and A. W. Westerberg. AS-
CEND: An Object-Oriented Computer Environment for Modeling
and Analysis: The Modeling Language. Computers chem. Engng.,15
(1):53–72, 1991.
S. Räumschüssel, A. Gerstlauer, E. D. Gilles, B. Raichle, M. Zeitz, and
W. Marquardt. An Architecture of a Knowledge-Based Process Mod-
eling and Simulation Tool. In Proc. IMACS/IFAC 2nd Intl. Symposium
on Mathematical and Intelligent Models in System Simulation,volume2,
pages 242–247, 1993.
J. Rekers and A. Schürr. A Graph Grammar Approach to Graphical
Parsing. Technical Report 95-15, Department of Computer Science,
Leiden University, 1995.
G. Rozenberg, editor. Handbook of Graph Grammars and Computing by
Graph Transformation, volume 1 Foundations. World Scientific, 1997.
G. Rozenberg and E. Welzl. Boundary NLC Graph Grammars—Basic
Definitions, Normal Forms, and Complexity. Information and Control,
69:136–167, 1986.
A. Schulz. Graphenanalyse hydraulischer Schaltkreise zur Erkennung
von hydraulischen Achsen und deren Kopplung. Master’s thesis,
University of Paderborn, Department of Mathematics and Com-
puter Science, 1997.
A. Schürr. Introduction to PROGRESS, an Attribute Graph Grammar
Based Specification Language. In M. Nagl, editor, Proc. 15th Intl.
Workshop on Graph-Theoretic Concepts in Computer Science,volume411
of LNCS, pages 151–165. Springer-Verlag, 1989.
A. Schürr. PROGRES: A VHL-Language Based on Graph Grammars.
In H. Ehrig, H.-J. Kreowski, and G. Rozenberg, editors, Proc. 4th Intl.
Workshop on Graph Grammars and Their Application to Computer Sci-
ence, volume 532 of LNCS, pages 641–659. Springer-Verlag, 1991.
117
Bibliography
A. Schürr. Developing Graphical (Software Engineering) Tools with
PROGRES. In Proc. ICSE, pages 618–619. IEEE Computer Society
Press, 1997a.
A. Schürr. Programmed Graph Replacement Systems. In G. Rozen-
berg, editor, Handbook of Graph Grammars and Computing by Graph
Transformation, pages 479–546. World Scientific, Singapore, 1997b.
A. Schürr, A. Winter, and A. Zündorf. Visual Programming with Graph
Rewriting Systems. In Proc. 11th Intl. IEEE Symposium on Visual Lan-
guages. IEEE Computer Society Press, 1995.
R. Schuster. Graphgrammatiken und Grapheinbettungen: Algorithmen und
Komplexität. PhD thesis, Universität Passau, 1987.
A. Slisenko. Context-Free Grammars as a Tool for Describing
Polynomial-Time Subclasses of Hard Problems. Inf. Proc. Letters, 14:
52–56, 1982.
B. Stein. Functional Models in Configuration Systems. PhD thesis, Uni-
versity of Paderborn, 1995.
B. Stein. Model Construction in Analysis and Synthesis Tasks. Professo-
rial dissertation (to appear), University of Paderborn, Department
of Mathematics and Computer Science, 2001.
B. Stein and M. Hoffmann. On Adaptation in Case-Based Design. In
R. Parenti and F. Masulli, editors, Proc. 3rd Intl. Symposia on Intelligent
Industrial Automation & Soft Computing. ICSC Academic Press, 1999.
B. Stein and A. Schulz. Topological Analysis of Hydraulic Systems.
Technical Report tr-ri-98-197, University of Paderborn, 1998.
B. Stein and E. Vier. An Approach to Formulate and to Process Design
Knowledge in Fluidics. In N. E. Mastorakis, editor, Recent Advances
in Information Science and Technology, pages 237–242. World Scientific
Publishing, 1998.
G. Stephanopoulos, G. Henning, and H. Leone. Model.la. A Model-
ing Language for Process Engineering - I. The Formal Framework.
Computers chem. Engng., 14(1):813–846, 1990.
118
Bibliography
M. van Eekelen, S. Smetsers, and R. Plasmeijer. Graph Rewriting
Systems for Functional Programming Languages. Technical report,
Computing Science Institute, University of Nijmegen, 1998.
119
Bibliography
120
A Applications in Design
Within this thesis we have concentrated on important tasks related to
the design of technical systems: analysis, synthesis and optimization
of structures. These are tasks located at a global level with respect to
the overall design of a system. Additionally, there are a series of other
tasks that play a minor role within the design process but that are
nonetheless necessary within certain contexts. Some of these special
tasks can be tackled by means of design graph grammars.
As hinted in section 3.1, there are various conceivable operations
on structures, and some of the examples presented there belong to
special tasks as mentioned above. The following examples stem from
work on projects dealing with design aspects in different domains and
address tasks located at the global level as well as tasks for more re-
stricted purposes.
121
A Applications in Design
A.1 Structural Synthesis: Chemical Plants
Throughout this thesis short examples from the domain of chemical
engineering have been used to exemplify the use of design graph
grammars for synthesis tasks; however, none of the presented exam-
ples was based on a complete design graph grammar—up to now only
excerpts were used. Now we present a complete design graph gram-
mar with which simple chemical plants can be derived.
Due to lack of space the granularity of the design graph grammar
has to be restricted, as described in the following.
•Available unit-operations. There are many devices that can be used
for the same task (heating, conveying, mixing). In order to keep
the rule set compact, we limit the available unit-operations to
one heat transfer unit-operation, one conveying unit-operation
and two mixing unit-operations for low and high viscous sub-
stances. Additionally, two combined mixing and heat transfer
unit-operations are allowed. The figure below shows the avail-
able unit-operations.
•Substance properties. The most relevant substance properties are
temperature, viscosity and state. Further properties of impor-
tance are density, heat capacity etc., but we refrain from taking
these into consideration here.
•Label class granularity. For each scalar substance property we
choose to use a label consisting of two different variants: “low”
and “high”. Thus, temperature is represented by tland th,and
viscosity by vland vh. The property state is represented by sg,sl
and ss, corresponding to the three states “gaseous”, “liquid” and
“solid”.
Let G=Σ,P,sbe a design graph grammar for the synthesis of
chemical plants where Σ={s,s,p,h,mpropeller,manchor,hmpropeller,
122
A.1 Structural Synthesis: Chemical Plants
hmanchor,A,B,C,H,I},sis the initial symbol (unused here1)andP
is the set of graph transformation rules, which are divided into prop-
erty related groups as follows:
State related graph transformation rules:
•Splitting rule for solids and fluids
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 3),sl),((2, 3),ss)}
R=VR,ER,
σ
R={4, 5, 6, 7},{(4, 6),(5, 6),(6, 7)},
{(4, A),(5, B),(6, C),(7, C),((4, 6),sl),((5, 6),ss)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,7,I))}
The graphical representation of the above rule is as follows:
ss
A
B
C
slC
sl
ss
A
B
slC
Splitting rule for liquids and gases
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 3),sl),((2, 3),sg)}
R=VR,ER,
σ
R={4, 5, 6, 7},{(4, 6),(5, 6),(6, 7)},
{(4, A),(5, B),(6, C),(7, C),((4, 6),sl),((5, 6),sg)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,7,I))}
The formal representation corresponds to the following graphi-
cal rule:
1This design task requires an initial graph consisting of a set of inputs connected to a
“plant” node, which is in turn connected to an output.
123
A Applications in Design
sg
A
B
slCC
sl
sg
A
B
slC
•Improvement of solubility by heating
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 3),sl),((2, 3),ss)}
R=VR,ER,
σ
R={4, 5, 6, 7, 8},{(4, 6),(5, 8),(6, 7),
(7, 8)},{(4, A),(5, B),(6, h),(7, p),(8, C),
((4, 6),sl),((5, 6),ss)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,C,I))}
The graphical rule representing the above formal rule is as fol-
lows:
ss
A
C
B
sl
ss
A
C
B
slth
Temperature related graph transformation rules:
•Improvement of mixing properties by heating an input
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 2),tl),((2, 3),th)}
R=VR,ER,
σ
R={4, 5, 6, 7, 8},{(4, 5),(5, 6),(6, 7),
(7, 8)},{(4, A),(5, h),(6, p),(7, B),(8, C),
124
A.1 Structural Synthesis: Chemical Plants
((4, 5),tl),((6, 7),th),((7, 8),th)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,C,I))}
The graphical representation of the above rule is as follows:
A
C
B
tl
th
A
CB th
tlth
Improvement of mixing properties by cooling an input
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 2),th),((2, 3),tl)}
R=VR,ER,
σ
R={4, 5, 6, 7, 8},{(4, 5),(5, 6),(6, 7),
(7, 8)},{(4, A),(5, h),(6, p),(7, B),(8, C),
((4, 5),th),((6, 7),tl),((7, 8),tl)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,C,I))}
The graphical representation of the above rule is as follows:
A
C
B
th
tl
A
CB tl
thtl
•Improvement of mixing properties by dealing with warm inputs
separately
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
125
A Applications in Design
(3, C),((1, 2),th),((2, 3),th)}
R=VR,ER,
σ
R={4, 5, 6, 7},{(4, 6),(5, 6),(6, 7)},
{(4, A),(5, B),(6, C),(7, C),
((4, 6),th),((5, 6),th),((6, 7),th)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,7,I))}
The formal notation yields the following graphical rule:
th
A
B
C
ththC
th
A
B
thC
Improvement of mixing properties by dealing with cold inputs
separately
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 2),tl),((2, 3),tl)}
R=VR,ER,
σ
R={4, 5, 6, 7},{(4, 6),(5, 6),(6, 7)},
{(4, A),(5, B),(6, C),(7, C),
((4, 6),tl),((5, 6),tl),((6, 7),tl)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,7,I))}
The formal notation yields the following graphical rule:
tl
A
B
C
tltlC
tl
A
B
tlC
126
A.1 Structural Synthesis: Chemical Plants
•Aggregation of mixer and heating chain into combined device
(optimization)
T=VT,ET,
σ
T={1, 2, 3},{(1, 2),(2, 3)},
{(1, mpropeller),(2, p),(3, h)}
R=VR,ER,
σ
R={4},{},{(4, hmpropeller)}
I={((H,mpropeller,I),(H,hmpropeller,I)),
((H,h,I),(H,hmpropeller,I))}
The rule described above corresponds to the following graphical
representation:
Aggregation of mixer and heating chain into combined device
(optimization)
T=VT,ET,
σ
T={1, 2, 3},{(1, 2),(2, 3)},
{(1, manchor),(2, p),(3, h)}
R=VR,ER,
σ
R={4},{},{(4, hmanchor)}
I={((H,manchor,I),(H,hmanchor,I)),
((H,h,I),(H,hmanchor,I))}
The above rule corresponds to the following graphical represen-
tation:
Viscosity related graph transformation rules:
•Choice of mixer for lower viscous inputs
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
127
A Applications in Design
(3, ?),((1, 2),vh)}
R=VR,ER,
σ
R={4, 5, 6},{(4, 6),(5, 6)},
{(4, A),(5, B),(6, manchor),((4, 6),vh)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,manchor,I))}
The following graphical rule represents the above formal rule:
A
?
B
vh
A
B
vh
Choice of mixer for high viscous inputs
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, ?),((1, 2),vl)}
R=VR,ER,
σ
R={4, 5, 6},{(4, 6),(5, 6)},
{(4, A),(5, B),(6, mpropeller),((4, 6),vh)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,mpropeller,I))}
The formal notation yields the following graphical rule:
A
?
B
vl
A
B
vl
128
A.1 Structural Synthesis: Chemical Plants
•Improvement of mixing properties by dealing with high viscous
inputs separately
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 2),vh),((2, 3),vh)}
R=VR,ER,
σ
R={4, 5, 6, 7},{(4, 6),(5, 6),(6, 7)},
{(4, A),(5, B),(6, C),(7, C),
((4, 6),vh),((5, 6),vh),((6, 7),vh)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,7,I))}
The formal notation yields the following graphical rule:
vh
A
B
C
vhvhC
vh
A
B
vhC
•Improvement of mixing properties by heating high viscous input
T=VT,ET,
σ
T={1, 2, 3},{(1, 3),(2, 3)},{(1, A),(2, B),
(3, C),((1, 3),vh),((2, 3),vl)}
R=VR,ER,
σ
R={4, 5, 6, 7, 8},{(4, 6),(5, 8),(6, 7),
(7, 8)},{(4, A),(5, B),(6, h),(7, p),(8, C),
((4, 6),vh),((5, 8),vl),((7, 8),th)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I)),
((H,C,I),(H,C,I))}
The graphical rule representing the above formal rule is as fol-
lows:
129
A Applications in Design
A
C
B
vh
A
C
B
vh
vlvl
th
Remarks.
Please note that the substance property under consideration
determines the types of structural manipulation that are necessary. For
instance, all properties lead to splitting rules, the property “tempera-
ture” is connected to optimization rules, and the property “viscosity”
implies choice rules. Likewise, the other substance properties not cov-
ered by the design graph grammar described above are also associated
with specific structural transformations.
The rule set presented above suffices to generate graphs corre-
sponding to simple chemical plants; any remaining “?” labeled nodes
are superfluous and can be deleted—this could also have been done
by means of a design graph grammar rule.
130
A.2 Structural Simplification: Hydraulic Plants
A.2 Structural Simplification: Hydraulic Plants
The maintenance of hydraulic plants is a challenging job for present-
day engineers. The size and complexity of hydraulic plants exceed the
human capacity to manage them efficiently, thus making additional
support a necessity. In special, the design task “analysis” for diagnosis
purposes is of importance.
In [Schulz,1997,Stein and Schulz,1998] the concept of hydraulic
axes plays a major role within the analysis of a hydraulic plant. Hy-
draulic axes represent substructures within a hydraulic plant that per-
form a function; the recognition of all hydraulic axes of a hydraulic
plant yields the set of all functions present within the plant—in a cer-
tain sense one could say the recognition of hydraulic axes is the recog-
nition of the building blocks that compose the global plant. Figure A.1
shows a hydraulic plant and its hydraulic axes.
Figure A.1: A hydraulic plant containing three hydraulic axes (shaded
areas); the fourth area is shared by all axes.
The recognition of the hydraulic axes of a plant does not suffice
to fully analyze a hydraulic plant. Within the diagnosis context the
knowledge about the relationships between the individual axes is es-
sential for a precise statement concerning a faulty component, since a
131
A Applications in Design
defect within a hydraulic axis often influences the behavior of other
axes, spreading the faulty behavior throughout the hydraulic plant.
Thus, the relationship between each pair of hydraulic axes within a
hydraulic plant must be considered. Figure A.2 shows the couplings
between the hydraulic axes depicted in Figure A.1.
sequential
serial
Figure A.2: Coupling of hydraulic axes.
The tasks described above—the recognition of hydraulic axes and
of their relationship to each other—are efficiently solved by means of
path search algorithms. This is due to the inherent structure of hy-
draulic axes; each hydraulic axis possesses a pump, representing a
pressure source, some valves for control together with additional aux-
iliary components, and cylinders and motors, representing the work-
ing devices responsible for the output. However, hydraulic axes often
possess substructures that hinder a full recognition: circuit loops, dead
branches etc. Thus, a hydraulic circuit has to be simplified prior to ap-
plying path searching methods; Figure A.3 illustrates the simplifica-
tion process.
The following simple design graph grammar suffices to perform
the transformation described by Figure A.3.
132
A.2 Structural Simplification: Hydraulic Plants
Figure A.3: Simplification of a hydraulic circuit by structural compres-
sion and merging.
First, let the following assumptions be made:
•Supply elements, i. e., pumps and tanks, are designated by the
label “p”,
•Working elements, i. e., cylinders and motors, are represented by
the label “w”,
•Control elements, i. e., valves, are designated by the label “v”,
•Junction nodes, also called Tri-Connections, are represented by the
label “j”,
•and all other auxiliary elements are designated by the label “a”.
133
A Applications in Design
Let G=Σ,P,sbe a design graph grammar for the structural
simplification of hydraulic circuits where Σ={p,w,v,j,a,s,H,I,J,
K,L,M,N},sis the initial symbol (unused here) and P=Pcompression ∪
Pmerging is the set of graph transformation rules.
Now, we first provide the compression related graph transforma-
tion rules Pcompression:
1. Compression of dead branches
T=VT,ET,
σ
T={1, 2},{{1, 2}},{(1, a),(2, K)}
R=VR,ER,
σ
R={3},{},{(3, K)}
I={((J,K,H),(J,K,H))}
The graphical representation of this rule is as shown below.
LK L
2. Compression of chains
T=VT,ET,
σ
T={1, 2, 3},{{1, 2},{2, 3}},
{(1, H),(2, a),(3, K)}
R=VR,ER,
σ
R={4, 5},{{4, 5}},{(4, H),(5, K)}
I={((I,H,M),(I,H,M)),((J,K,M),(J,K,M))}
The graphical representation of this rule is depicted below.
aKH KH
3. Compression of loops
T=VT,ET,
σ
T={1, 2, 3, 4},{{1, 2},{1, 3},
{2, 4},{3, 4}},{(1, j),(2, a),(3, a),(4, j)}
R=VR,ER,
σ
R={5},{},{(5, j)}
I={((H,j,I),(H,j,I))}
The graphical representation of this rule is illustrated below.
134
A.2 Structural Simplification: Hydraulic Plants
a
a
j
jj
The set of graph transformation rules Pmerging is defined as follows:
1. Merging with working elements
T=VT,ET,
σ
T={1, 2},{{1, 2}},{(1, w),(2, K)}
R=VR,ER,
σ
R={3},{},{(3, w)}
I={((H,w,L),(H,w,L)),((J,K,M),(J,w,M))}
The above formal representation is equivalent to the following
graphical notation:
wK w
2. Merging with supply elements
T=VT,ET,
σ
T={1, 2},{{1, 2}},{(1, p),(2, K)}
R=VR,ER,
σ
R={3},{},{(3, p)}
I={((J,K,M),(J,p,M))}
The graphical representation of the above graph transformation
rule is as follows:
pK p
3. Merging with control elements
T=VT,ET,
σ
T={1, 2},{{1, 2}},{(1, v),(2, K)}
R=VR,ER,
σ
R={3},{},{(3, v)}
I={((H,v,M),(H,v,M)),((J,K,N),(J,v,N))}
135
A Applications in Design
Again, the corresponding graphical representation is depicted
below:
vK v
Remarks.
Some of the above graph transformation rules possess iden-
tical structures and differ only with respect to node and edge labels.
In such cases one could argue that label classes would reduce the num-
ber of graph transformation rules noticeably. For example, all merging
rules could be written as a single rule using label classes; however, the
embedding instructions would have to be adapted to match the most
general case.
136
A.3 Structural Synthesis: Hydraulic Plants
A.3 Structural Synthesis: Hydraulic Plants
Like the analysis task described in section A.2, structural synthesis
also represents a major challenge due to the same reasons. One way
to tackle this job is to use case-based reasoning techniques to derive
solutions from previously solved tasks. In [Stein and Hoffmann,1999],
Stein and Hoffmann introduce abstract building blocks that are com-
bined to form new hydraulic plants; the concrete plant parts corre-
sponding to the abstract building blocks are retrieved from a case
database and adapted accordingly. Figure A.4 illustrates this notion.
w w
c
c
s
Figure A.4: Example of a concrete hydraulic plant and its abstract
building block view.
The following design graph grammar generates feasible structures
consisting of abstract building blocks; a subsequent case-based pro-
cessing step can then convert these abstract structures into concrete
hydraulic circuits.
First, let the following assumptions be made:
•Functional units are labeled with “f”,
•Supply elements, i. e., pumps and tanks, are designated by the
label “s”,
•Working elements, i. e., cylinders and motors, are represented by
the label “w”,
•Control elements, i. e., valves, are designated by the label “c”,
137
A Applications in Design
•Junction nodes, also called Tri-Connections, are represented by the
label “t”,
•and all other auxiliary elements are designated by the label “b”.
Let G=Σ,P,?be a design graph grammar for the structural syn-
thesis of hydraulic circuits where Σ={?, f,s,w,c,t,b,A,B},?isthe
initial symbol and Pis the set of graph transformation rules.
The graph transformation rules in Pare as follows:
1. Generation of a functional unit
?fbb
s
2. Refinement of a functional unit into a hydraulic axis
fwbb
c
3. Removal of auxiliary node
bBAAB
4. Insertion of a further functional unit in series
fbbfbbfb
5. Insertion of a further functional unit in parallel
fbb
fb
b
ft
tbb
138
A.3 Structural Synthesis: Hydraulic Plants
6. Insertion of a further hydraulic axis in parallel
wbbwb
b
wt
tbb
7. Insertion of a further hydraulic axis in sequence
wbb
w
w
bb
ttbb
c
Finally, the appearance used for Figure A.4 is achieved by means
of an additional design graph grammar with the following four graph
transformation rules:
ww
ss
t c c
139
A Applications in Design
A.4 Model Reformulation: Wave Digital Structures
Wave digital structures (WDS) form a particular class of signal flow
graphs where the signals are linear combinations of the electric cur-
rent and flow. WDS represent a concept to translate electrical circuits
from the electrical u/i-domain into the a/b-wave-domain; this trans-
lation establishes a paradigm shift and is called, in terms of models,
model reformulation. With respect to this concrete example, this refor-
mulation is bound up with several advantages, which are addressed
in [Fettweis,1986].
When migrating from an electrical circuit towards a WDS, the un-
derlying model is completely changed: The structure model of the
electrical circuit, Mu/i
S, is interpreted as a series-parallel graph with
closely connected components and transformed into an adaptor struc-
ture, Ma/b
S.
Figure A.5 shows the reformulation of a series-parallel structure
tree of an electrical circuit into a corresponding adaptor structure. The
nodes labeled by “s” and “p” indicate series and parallel connections
in the circuit.
p
s
s
p
12
345
67
89
1
2
8
9
3
4
5
6
7
p
sSeries connection
Parallel connection
Series adaptor
Parallel adaptor
Figure A.5: Overview of the mapping Mu/i
S−→ Ma/b
S.
The following design graph grammar2performs the model refor-
mulation depicted in Figure A.5 for arbitrary structure models Mu/i
S.
2Since the involved transformation is a translation rather than generation, it would be
better to speak of graph transformation systems instead of graph grammars.
140
A.4 Model Reformulation: Wave Digital Structures
G=Σ,P,zwith Σ={z,p,s,i,X,Y,A,B,C,D,E,F,G,H,I,J},
zis the initial symbol (can be neglected), and Pis the set of graph
transformation rules, which are presented in the following.
1. Splitting rule for nodes with more than three edges.
T=VT,ET,
σ
T={1, 2, 3, 4, 5},{{1, 5},{2, 5},
{3, 5},{4, 5}},{(1, E),(2, F),(3, G),(4, H),
(5, X),({1, 5},B),({2, 5},A),({3, 5},C),
({4, 5},D)}
R=VR,ER,
σ
R={6, 7, 8, 9, 10, 11},
{{6, 7},{7, 8},{7, 9},{9, 10},{9, 11}},
{(6, F),(7, X),(8, E),(9, X),(10, G),(11, H),
({6, 7},A),({7, 8},B),({7, 9},i),({9, 10},C),
({9, 11},D)}
I={((F,X,A),(F,7,A)),((E,X,B),(E,7,B)),
((G,X,C),(G,9,C)),((H,X,D),(H,9,D)),
((I,E,J),(I,E,J)),((I,F,J),(I,F,J)),
((I,G,J),(I,G,J)),((I,H,J),(I,H,J))}
For illustrative reasons we resort to the graphical representation
from now on and refrain from using the formal version if appro-
priate.
XX
i
X
A
BCDCD
A
B
E
F
G
H
E
F
G
H
2. Marking rule for edges connecting inner nodes.
141
A Applications in Design
XY YX i
ABAB
The above rules are sufficient to perform the structural transforma-
tion required. The following rules belonging to an additional design
graph grammar are necessary to change the appearance of the final
structure into an adaptor structure as depicted in Figure A.5.
1. Display of a parallel node.
P
2. Display of a serial node.
S
3. Display of a port node. X
X
Z
Z
4. Display of node connector. XX
i
AA
142
A.5 Model Reformulation: Parallel-Series Graphs
A.5 Model Reformulation: Parallel-Series Graphs
Model reformulation, as motivated in section A.4, occurs in various
forms and within different contexts; however, many of them share the
same basic prerequisites and goals. The model reformulation task of
translating a structure description tree, such as the one depicted by
Figure A.5, into a parallel-series graph represents an adequate abstrac-
tion of the corresponding tasks within concrete technical domains.
In a certain sense the goal of this model reformulation task is to
translate the structural view of the system of interest into its topolog-
ical view. The initial structure is a structure description tree: Inner
nodes represent either parallel or serial parts of the described struc-
ture, leaves represent edge labels. Figure A.6 shows a structure de-
scription tree and the corresponding parallel-series graph.
pR
p
ss
∆∆∆
∆∆
∆
∆
∆
∆
∆
Figure A.6: A structure description tree and its corresponding paral-
lel-series graph.
The following design graph grammar performs the transformation
required by the model reformulation task.
G=Σ,P,zwith Σ={z,pR,sR,p0,s0,p,s,e,l,r,∆,A,B,H,I,J,
K,L,M},zis the initial symbol (can be neglected), and Pis the set of
graph transformation rules, which are presented in the following.
1. Initial rule for parallel rooted description tree
T=VT,ET,
σ
T={1},{},{(1, pR)}
R=VR,ER,
σ
R={2, 3, 4},{{2, 3},{3, 4}},
143
A Applications in Design
{(2, p0),(3, p),(4, p0),({2, 3},l),({3, 4},r)}
I={((H,pR,I),(H,p,I))}
The rule formally described above corresponds to the following
graphical representation:
pRp'
p0p0
lr
2. Initial rule for serial rooted description tree
T=VT,ET,
σ
T={1},{},{(1, sR)}
R=VR,ER,
σ
R={2, 3, 4},{{2, 3{,{3, 4}},
{(2, s0),(3, s),(4, s0),({2, 3},l),({3, 4},r)}
I={((H,sR,I),(H,s,I))}
The graphical representation of the above rule is as follows:
sRs'
s0s0
lr
3. Creation of parallel threads
T=VT,ET,
σ
T={1, 2, 3, 4},{{1, 2},{2, 3},{2, 4}},
{(1, A),(2, p),(3, B),(4, s),({1, 2},l),({2, 3},r)}
R=VR,ER,
σ
R={5, 6, 7, 8},{{5, 6},{5, 7},{6, 8},
{7, 8}},{(5, A),(6, p),(7, s),(8, B),
({5, 6},l),({5, 7},l),({6, 8},r),({7, 8},r)}
I={((H,p,I),(H,p,I)),((H,s,I),(H,s,I)),
((H,A,I),(H,A,I)),((H,B,I),(H,B,I))}
The above rule corresponds to the following graphically:
144
A.5 Model Reformulation: Parallel-Series Graphs
p'
s
p'
s'
lr lr
lr
AB
AB
Creation of parallel threads containing a leaf node
T=VT,ET,
σ
T={1, 2, 3, 4},{{1, 2},{2, 3},{2, 4}},
{(1, A),(2, p),(3, B),(4, ∆),({1, 2},l),({2, 3},r)}
R=VR,ER,
σ
R={5, 6, 7, 8},{{5, 6},{5, 7},{6, 8},
{7, 8}},{(5, A),(6, p),(7, ∆),(8, B),
({5, 6},l),({5, 7},l),({6, 8},r),({7, 8},r)}
I={((H,p,I),(H,p,I)),((H,A,I),(H,A,I)),
((H,B,I),(H,B,I))}
The graphical representation is:
p' p'
lr lr
lr
∆
∆
AB
AB
4. Removal of empty parallel node
T=VT,ET,
σ
T={1, 2, 3},{{1, 2},{2, 3}},
{(1, A),(2, p),(3, B),({1, 2},l),({2, 3},r)}
R=VR,ER,
σ
R={4, 5},{},{(4, A),(5, B)}
I={((H,A,L),(H,A,L)),((H,B,L),(H,B,L))}
The formal definition of the above rule conforms with the fol-
lowing graphical representation:
145
A Applications in Design
p'
lr
AB AB
5. Creation of serial thread
T=VT,ET,
σ
T={1, 2, 3, 4},{{1, 2},{2, 3},
{2, 4}},{(1, A),(2, s),(3, B),(4, p),
({1, 2},l),({2, 3},r)}
R=VR,ER,
σ
R={5, 6, 7, 8, 9},{{5, 6},{6, 7},
{7, 8},{8, 9}},{(5, A),(6, p),(7, e),(8, s),
(9, B),({5, 6},l),({6, 7},r),({7, 8},l),({8, 9},r)}
I={((H,s,I),(H,s,I)),((H,p,I),(H,p,I)),
((H,A,I),(H,A,I)),((H,B,I),(H,B,I))}
The graphical rule depicted below reflects the above formal def-
inition:
p
s'
lr
AB
p' s'
lr
AB
lr
e
Creation of a serial thread containing a leaf node
T=VT,ET,
σ
T={1, 2, 3, 4},{{1, 2},{2, 3},
{2, 4}},{(1, A),(2, s),(3, B),(4, ∆),
({1, 2},l),({2, 3},r)}
R=VR,ER,
σ
R={5, 6, 7, 8, 9},{{5, 6},{6, 7},
{7, 8},{8, 9}},{(5, A),(6, ∆),(7, e),(8, s),
(9, B),({5, 6},l),({6, 7},r),({7, 8},l),({8, 9},r)}
I={((H,s,I),(H,s,I)),((H,A,I),(H,A,I)),
((H,B,I),(H,B,I))}
146
A.5 Model Reformulation: Parallel-Series Graphs
Again, the rule described above corresponds to the following
graphical representation:
s'
lr
∆
A B s'
lr
∆
A Be
r l
6. Removal of empty serial node
T=VT,ET,
σ
T={1, 2∗,3},{{1, 2},{2, 3}},
{(1, A),(2, s),(3, B),({1, 2},l),({2, 3},r)}
R=VR,ER,
σ
R={4},{},{(4, A)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,A,I))}
Once again, the above formal description corresponds to the fol-
lowing graphical representation:
l r
s'
AB A
7. Creation of a labeled edge
T=VT,ET,
σ
T={1, 2, 3},{{1, 2},{2, 3}},
{(1, A),(2, ∆),(3, B),({1, 2},l),({2, 3},r)}
R=VR,ER,
σ
R={4, 5},{{4, 5}},{(4, A),(5, B),
({4, 5},∆)}
I={((H,A,I),(H,A,I)),((H,B,I),(H,B,I))}
lr
∆∆
AB AB
147
A Applications in Design
Remarks.
As with the rules presented in section A.2,theuseoflabel
classes would result in a smaller rule set by combining all graph trans-
formation rules with identical oder nearly identical structures. Again,
theembeddinginstructionswouldhavetobeadaptedtomatchthe
most general case.
Example.
Figure A.7 illustrates the usage of the design graph grammar
described above.
Remarks.
This design graph grammar allows for parallelism, which
was implicitly used in the derivation shown in Figure A.7.
148
A.5 Model Reformulation: Parallel-Series Graphs
pR
p
ss
∆∆∆
∆∆
p
ss
∆∆∆
∆∆
p'p0p0
lr
p
s
s'
∆
∆∆
∆∆
p'
p0p0
lr
lr
p
s'
s'
∆
∆
∆
∆∆
p'
p0p0
lr
lr
lr
∆∆
∆
∆
p0p0
lr
e
∆
e
∆∆
∆
∆
p0p0
e
∆
e
p' s'
s'
∆
∆
∆∆
p0p0
l
r
lr
el
r
∆
e
lr
p'
∆
∆
∆
∆
p0p0
l
r
lr
e
∆
e
lr
l
r
Figure A.7: Translation of a structure description tree into a parallel-
series graph.
149
Index
algorithm
analysis-step, 41–42
synthesis-step, 52–53
compilation, 60
connecting approach, 74–77
context, 23–24
context graph, see graph
cut nodes, 28
deletion operation, 106, 106,107,
110
derivation, 30,104, 105, 108
leftmost, 93, 93–94, 95
rule sequence, 106
shortest, 104,105,107,108
step, 30
design graph grammar
boundary, 94–95, 95
context-free, 29–30
context-sensitive, 32–33
design process, 39
embedding instructions, 29
gluing approach, 77–79
graph
context, 28
host, 28
labeled, 22
ordered, 93
replacement, 28
rooted flowgraph, 101
target, 28
graph distance
derivational, 108–110
direct, 108
graph grammar
graph-based, 33–34
NCE, 74,75, 76–77, 100
neighborhood uniform, 31
NLC, 74, 74–75, 100
node-based, 33–34
precedence, 96,100,101
graph isomorphism, 22–23
with labels, 22–23
graph isomorphism problem, 88
host graph, see graph
HR grammar, 78
label alphabet, 29
label distance, 58
language
flowgraph, 101
rooted context-free flow-
graph, 100
location specifier, 65
matching, 23–24, 86
strict degree, 24
maximal common subgraph prob-
lem, 110
membership problem, 41,43,95,
100
model simplification, 7
approximation, 9
behavioral simplification, 9
150
Index
causal decomposition, 9,55
derived relationships, 11
entity aggregation
by function, 10
by structure, 11
function aggregation, 11
limited input space, 9
model boundary simplifica-
tion, 7
model context, 8
numeric representation, 10
simple task assumption, 7
state aggregation, 10
temporal aggregation, 10
modification
characteristics, 64
global, 64
local, 64
parameter, 64
ordered spanning tree, 101
PGRS, 85,105
principle of least commitment, 37
productions, 29
property
associativity, 91
confluence, 91,100
finite Church Rosser, 100
monotonicity, 106–107, 110
shortcut-free, 107
replacement graph, see graph
subgraph isomorphism problem,
88
subgraph matching problem, 43,
55,86,88,95,99,110
target graph, see graph
transformation rules, see produc-
tions
variable label, 29
bound, 37
unbound, 37
151
