GRAPH GRAMMAR (Sequential)
| Collection | International Encyclopedia of Systems and Cybernetics |
|---|---|
| Year | 2004 |
| Vol. (num.) | 2(1) |
| ID | ◀ 1462 ▶ |
| Object type | Discipline oriented, Methodology or model |
D. GERNERT explains how graphs can be rewrited, thus generating a sequential graph grammar through embedding rules . He describes as follows some important properties of this type of representation graphs:
1.The new graph generated by a production rule can be “more complex”or “less complex” than the old one
2.The continuation of the rewriting process is not necessarily unique: there may be non-determinism as well as determinism, or a combination of both, depending on the features of the individual graph grammar
3.There may be different sequences of derivation steps which lead to the same result, the “genesis” of a graph is not necessarily unique
4.A sequence of derivation steps can lead to the start graph again: “periodic graph grammars” are possible
5.In degenerate cases it may happen that none of the production rules are applicable so that the procedure stops
See also
Graph (Parallel rewriting of a), Rewriting