164:
54:
Graph transformations can be used as a computation abstraction. The basic idea is that if the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be
765:
Graphs are an expressive, visual and mathematically precise formalism for modelling of objects (entities) linked by relations; objects are represented by nodes and relations between them by edges. Nodes and edges are commonly typed and attributed. Computations are described in this model by changes
713:
and logical programming since they are well-suited to representing quantified statements in first order logic. Symbolic programming software is another application for term graphs, which are capable of representing and performing computation with abstract algebraic structures such as groups, fields
725:
Graph rewriting systems naturally group into classes according to the kind of representation of graphs that are used and how the rewrites are expressed. The term graph grammar, otherwise equivalent to graph rewriting system or graph replacement system, is most often used in classifications. Some
650:
From the practical perspective, the key distinction between DPO and SPO is how they deal with the deletion of nodes with adjacent edges, in particular, how they avoid that such deletions may leave behind "dangling edges". The DPO approach only deletes a node when the rule specifies the deletion of
155:; the different wording is used to emphasize the goal of constructions, like the enumeration of all graphs from some starting graph, i.e. the generation of a graph language – instead of simply transforming a given state (host graph) into a new state.
766:
in the relations between the entities or by attribute changes of the graph elements. They are encoded in graph rewrite/graph transformation rules and executed by graph rewrite systems/graph transformation tools.
823:, a Java-based tool set for editing graphs and graph transformation rules, exploring the state spaces of graph grammars, and model checking those state spaces; can also be used as a graph transformation engine.
647:
diagram. Practical understanding of this is similar to the DPO approach. The difference is, that there is no interface between the host graph G and the graph G' being the result of the rewriting step.
682:. In this approach, graphs are treated as database instances, and rewriting operations as a mechanism for defining queries and views; therefore, all rewriting is required to yield unique results (
264:
709:. Term graphs are also used as abstract machines capable of modelling chemical and biological computations as well as graphical calculi such as concurrency models. Term graphs can perform
950:
is an interpreter and UI environment for creating unrestricted graph grammars as well as testing and searching the resultant language variant. It saves graphs and graph grammar rules as
296:
641:
428:
388:
322:
86:
686:), and this is achieved by applying any rewriting rule concurrently throughout the graph, wherever it applies, in such a way that the result is indeed uniquely defined.
128:
being called replacement graph (or right-hand side of the rule). A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph (
598:
578:
558:
538:
518:
498:
474:
454:
126:
106:
1204:
705:
Term graphs are a prominent topic in programming language research since term graph rewriting rules are capable of formally expressing a compiler's
580:
is needed to attach the pattern being matched to its context: if it is empty, the match can only designate a whole connected component of the graph
1132:
1347:
1318:
1282:
1176:
655:
can be checked for a given match), whereas the SPO approach simply disposes the adjacent edges, without requiring an explicit specification.
136:) and by replacing the found occurrence by an instance of the replacement graph. Rewrite rules can be further regulated in the case of
965:
658:
There is also another algebraic-like approach to graph rewriting, based mainly on
Boolean algebra and an algebra of matrices, called
1142:
955:
830:
814:
199:
193:
961:
477:
133:
32:
930:
989:
is a rule-based language for modeling systems of interacting agents, primarily motivated by molecular systems biology.
777:
773:
225:
1027:
912:
870:
792:
843:
644:
352:
1367:
730:
786:
is a visual rule-based graph programming language designed to facilitate formal reasoning over graph programs.
1201:
560:
serves as an interface, containing the nodes and edges which are preserved when applying the rule. The graph
269:
55:
matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph.
741:
to characterising replacements, mentioned in the above section on the algebraic approach to graph rewriting.
738:
734:
614:
401:
361:
968:
for graph transformation systems. Its main application focus is data analytics in the field of engineering.
710:
920:
853:
745:
706:
40:
1296:
1148:
717:
The TERMGRAPH conference focuses entirely on research into term graph rewriting and its applications.
916:
874:
839:
749:
171:
36:
301:
65:
1334:. Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 3. World Scientific.
1305:. Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 2. World Scientific.
1269:. Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 1. World Scientific.
862:
44:
191:. The algebraic approach is further divided into sub-approaches, the most common of which are the
1260:
1057:
1015:
604:
219:
933:, an integrated environment and very high level language for PROgrammed Graph REwriting Systems.
603:
In contrast a graph rewriting rule of the SPO approach is a single morphism in the category of
1343:
1314:
1278:
1248:
1172:
1138:
683:
1329:
1300:
1264:
1335:
1306:
1270:
1238:
1228:
976:
432:
129:
48:
20:
163:
1208:
866:
796:
753:
679:
188:
152:
803:
and transformation. It is an implementation of an extension of
Messmer’s algorithm using
698:
rewriting, which involves the processing or transformation of term graphs (also known as
1328:
Hartmut Ehrig; Hans-Jörg
Kreowski; Ugo Montanari; Grzegorz Rozenberg, eds. (Aug 1999).
1052:
924:
902:
886:
800:
583:
563:
543:
523:
503:
483:
459:
439:
111:
91:
1361:
1292:
1095:
1047:
137:
35:
out of an original graph algorithmically. It has numerous applications, ranging from
1042:
1011:
981:
1233:
1216:
1168:
1001:
695:
1252:
829:, a software specification and verification system based on graph rewriting (
214:
From the perspective of the DPO approach a graph rewriting rule is a pair of
898:
338:
325:
59:
1010:
is an
English-language parser that employs graph re-writing to convert a
356:
215:
174:
from compiler construction: multiplication with 2 replaced by addition).
1198:
Analysis and
Verification of Systems with Dynamically Evolving Structure
977:
Functional-structural plant modeling with a graph grammar based language
826:
789:
1190:
997:
982:
Multicellular development modeling with string-regulated graph grammars
883:
uses Story driven modelling, a graph rewrite language based on PROGRES.
1243:
783:
936:
813:, the graph rewrite generator, a graph transformation tool emitting
62:
system usually consists of a set of graph rewrite rules of the form
908:
804:
1007:
892:
810:
675:
162:
1339:
1310:
1274:
1134:
Handbook of Graph
Grammars and Computing by Graph Transformations
1096:"A Graph-Oriented Object Model for Database End-User Interfaces"
1215:
Lobo, Daniel; Vico, Francisco J.; Dassow, Jürgen (2011-10-01).
1112:
820:
1165:
Matrix Graph
Grammars: An Algebraic Approach to Graph Dynamics
951:
852:, an EMF-compliant model-transformation tool with support for
744:
Hypergraph grammars, including as more restrictive subclasses
986:
947:
178:
Application of the rule to optimize "y=x*2" into "y=x+x".
880:
187:
The algebraic approach to graph rewriting is based upon
859:
849:
617:
586:
566:
546:
526:
506:
486:
462:
442:
404:
364:
304:
272:
228:
114:
94:
68:
994:
1004:) which is used to implement various AI algorithms.
799:, the Graph Matching and Transformation Engine for
721:
Classes of graph grammar and graph rewriting system
108:being called pattern graph (or left-hand side) and
670:Yet another approach to graph rewriting, known as
635:
592:
572:
552:
532:
512:
492:
468:
448:
422:
382:
316:
290:
258:
120:
100:
80:
1217:"Graph grammars with string-regulated rewriting"
1191:Electronic Notes in Theoretical Computer Science
643:. Thus a rewriting step is defined by a single
430:models an occurrence of L in G and is called a
1137:, vol. 1–3, World Scientific Publishing,
259:{\displaystyle r=(L\leftarrow K\rightarrow R)}
140:, such as in string-regulated graph grammars.
398:-pushout comes from). Another graph morphism
8:
1060:— a generalization of graph rewriting
770:Tools that are application domain neutral:
31:, concerns the technique of creating a new
16:Creating a new graph from an existing graph
1331:Concurrency, Parallelism, and Distribution
1202:Habilitation thesis, Universität Stuttgart
901:, a graph-based programming language (see
889:often support dynamic rewriting of graphs.
436:. Practical understanding of this is that
1242:
1232:
915:, supporting in-place and model-to-model
873:, supporting in-place and model-to-model
616:
585:
565:
545:
525:
505:
485:
461:
441:
403:
363:
303:
271:
227:
113:
93:
67:
733:, typically formalised using either the
611:that preserve the multigraph structure:
1299:; Grzegorz Rozenberg, eds. (Oct 1999).
1075:
776:, the attributed graph grammar system (
702:) by a set of syntactic rewrite rules.
694:Another approach to graph rewriting is
291:{\displaystyle L\supseteq K\subseteq R}
636:{\displaystyle r\colon L\rightarrow R}
423:{\displaystyle m\colon L\rightarrow G}
383:{\displaystyle k\colon K\rightarrow D}
355:diagrams both originating in the same
1193:148 (1 SPEC. ISS.), pp. 187–198.
1082:
1030:is implemented using graph rewriting.
1000:provides a basic pattern matcher (on
911:, a graph rewriting system based on
7:
456:is a subgraph that is matched from
203:. Other sub-approaches include the
1187:Graph transformation in a nutshell
966:integrated development environment
869:a graph rewriting system based on
14:
1302:Applications, Languages and Tools
651:all adjacent edges as well (this
761:Implementations and applications
1085:covers this approach in detail.
480:), and after a match is found,
151:, especially in the context of
1023:Computer programming language
627:
414:
374:
317:{\displaystyle K\rightarrow L}
308:
253:
247:
241:
235:
218:in the category of graphs and
81:{\displaystyle L\rightarrow R}
72:
1:
944:Mechanical engineering tools
674:graph rewriting, came out of
200:single-pushout (SPO) approach
194:double-pushout (DPO) approach
1221:Theoretical Computer Science
1131:Rozenberg, Grzegorz (1997),
478:subgraph isomorphism problem
170:Example graph rewrite rule (
134:subgraph isomorphism problem
666:Determinate graph rewriting
1384:
1028:Clean programming language
856:and Triple Graph Grammars.
159:Graph rewriting approaches
1234:10.1016/j.tcs.2011.07.004
817:-code or .NET-assemblies.
731:Attributed graph grammars
147:is used as a synonym for
954:files and is written in
846:) with graph rewriting:
700:abstract semantic graphs
394:(this is where the name
328:. The graph K is called
51:and picture generation.
1196:König, Barbara (2004).
739:double-pushout approach
735:single-pushout approach
921:critical pair analysis
711:automated verification
637:
594:
574:
554:
534:
514:
494:
470:
450:
424:
384:
318:
292:
260:
179:
149:graph rewriting system
122:
102:
82:
973:Biology applications
854:Story-Driven Modeling
750:linear graph grammars
707:operational semantics
660:matrix graph grammars
638:
595:
575:
555:
535:
515:
495:
471:
451:
425:
385:
319:
293:
261:
166:
123:
103:
83:
45:software verification
41:software construction
1163:Perez, P.P. (2009),
840:software engineering
690:Term graph rewriting
615:
584:
564:
544:
524:
504:
484:
460:
440:
402:
362:
351:G is defined by two
302:
270:
226:
112:
92:
66:
37:software engineering
25:graph transformation
1185:Heckel, R. (2006).
746:port graph grammars
605:labeled multigraphs
220:graph homomorphisms
132:, thus solving the
1297:Hans-Jörg Kreowski
1263:, ed. (Feb 1997).
1261:Grzegorz Rozenberg
1211:, pp. 65–180.
1207:2007-06-25 at the
1058:Abstract rewriting
865:2016-04-22 at the
795:2018-03-13 at the
726:common types are:
653:dangling condition
633:
590:
570:
550:
530:
510:
490:
466:
446:
420:
380:
314:
288:
256:
183:Algebraic approach
180:
118:
98:
78:
58:Formally, a graph
1349:978-981-02-4021-9
1320:978-981-02-4020-2
1295:; Gregor Engels;
1284:978-981-02-2884-2
1227:(43): 6101–6111.
1178:978-3-639-21255-6
838:Tools that solve
684:up to isomorphism
593:{\displaystyle G}
573:{\displaystyle K}
553:{\displaystyle K}
533:{\displaystyle G}
513:{\displaystyle R}
500:is replaced with
493:{\displaystyle L}
469:{\displaystyle G}
449:{\displaystyle L}
347:of a rule r to a
332:or sometimes the
209:pullback approach
121:{\displaystyle R}
101:{\displaystyle L}
49:layout algorithms
1375:
1353:
1324:
1288:
1256:
1246:
1236:
1181:
1158:
1157:
1156:
1147:, archived from
1117:
1116:
1109:
1103:
1102:
1100:
1092:
1086:
1080:
1016:dependency parse
754:interaction nets
642:
640:
639:
634:
609:partial mappings
599:
597:
596:
591:
579:
577:
576:
571:
559:
557:
556:
551:
539:
537:
536:
531:
519:
517:
516:
511:
499:
497:
496:
491:
475:
473:
472:
467:
455:
453:
452:
447:
429:
427:
426:
421:
389:
387:
386:
381:
323:
321:
320:
315:
297:
295:
294:
289:
265:
263:
262:
257:
153:formal languages
130:pattern matching
127:
125:
124:
119:
107:
105:
104:
99:
87:
85:
84:
79:
21:computer science
1383:
1382:
1378:
1377:
1376:
1374:
1373:
1372:
1368:Graph rewriting
1358:
1357:
1356:
1350:
1327:
1321:
1291:
1285:
1259:
1214:
1209:Wayback Machine
1179:
1162:
1154:
1152:
1145:
1130:
1126:
1121:
1120:
1111:
1110:
1106:
1098:
1094:
1093:
1089:
1081:
1077:
1072:
1067:
1039:
903:Graph Rewriting
887:Graph databases
867:Wayback Machine
797:Wayback Machine
763:
723:
692:
680:database theory
668:
613:
612:
582:
581:
562:
561:
542:
541:
522:
521:
502:
501:
482:
481:
458:
457:
438:
437:
400:
399:
390:, where D is a
360:
359:
300:
299:
268:
267:
266:, also written
224:
223:
189:category theory
185:
161:
110:
109:
90:
89:
64:
63:
29:graph rewriting
17:
12:
11:
5:
1381:
1379:
1371:
1370:
1360:
1359:
1355:
1354:
1348:
1325:
1319:
1289:
1283:
1257:
1212:
1194:
1183:
1177:
1160:
1143:
1127:
1125:
1122:
1119:
1118:
1104:
1087:
1074:
1073:
1071:
1068:
1066:
1063:
1062:
1061:
1055:
1053:Formal grammar
1050:
1045:
1038:
1035:
1034:
1033:
1032:
1031:
1021:
1020:
1019:
1005:
992:
991:
990:
984:
979:
971:
970:
969:
959:
942:
941:
940:
934:
928:
925:model checking
917:transformation
906:
896:
890:
884:
878:
875:transformation
857:
842:tasks (mainly
836:
835:
834:
824:
818:
808:
801:graph matching
787:
781:
762:
759:
758:
757:
742:
722:
719:
691:
688:
667:
664:
632:
629:
626:
623:
620:
589:
569:
549:
529:
520:in host graph
509:
489:
465:
445:
419:
416:
413:
410:
407:
379:
376:
373:
370:
367:
313:
310:
307:
287:
284:
281:
278:
275:
255:
252:
249:
246:
243:
240:
237:
234:
231:
222:between them:
205:sesqui-pushout
184:
181:
160:
157:
138:labeled graphs
117:
97:
77:
74:
71:
15:
13:
10:
9:
6:
4:
3:
2:
1380:
1369:
1366:
1365:
1363:
1351:
1345:
1341:
1337:
1333:
1332:
1326:
1322:
1316:
1312:
1308:
1304:
1303:
1298:
1294:
1293:Hartmut Ehrig
1290:
1286:
1280:
1276:
1272:
1268:
1267:
1262:
1258:
1254:
1250:
1245:
1240:
1235:
1230:
1226:
1222:
1218:
1213:
1210:
1206:
1203:
1199:
1195:
1192:
1188:
1184:
1180:
1174:
1170:
1166:
1161:
1151:on 2013-10-04
1150:
1146:
1140:
1136:
1135:
1129:
1128:
1123:
1114:
1108:
1105:
1097:
1091:
1088:
1084:
1079:
1076:
1069:
1064:
1059:
1056:
1054:
1051:
1049:
1048:Shape grammar
1046:
1044:
1041:
1040:
1036:
1029:
1025:
1024:
1022:
1017:
1013:
1009:
1006:
1003:
999:
996:
995:
993:
988:
985:
983:
980:
978:
975:
974:
972:
967:
963:
960:
957:
953:
949:
946:
945:
943:
938:
935:
932:
929:
926:
922:
918:
914:
910:
907:
904:
900:
897:
894:
891:
888:
885:
882:
879:
876:
872:
868:
864:
861:
858:
855:
851:
848:
847:
845:
841:
837:
832:
828:
825:
822:
819:
816:
812:
809:
806:
802:
798:
794:
791:
788:
785:
782:
779:
775:
772:
771:
769:
768:
767:
760:
755:
751:
747:
743:
740:
736:
732:
729:
728:
727:
720:
718:
715:
712:
708:
703:
701:
697:
689:
687:
685:
681:
677:
673:
665:
663:
661:
656:
654:
648:
646:
630:
624:
621:
618:
610:
606:
601:
587:
567:
547:
527:
507:
487:
479:
463:
443:
435:
434:
417:
411:
408:
405:
397:
393:
392:context graph
377:
371:
368:
365:
358:
354:
350:
346:
342:
340:
335:
331:
327:
311:
305:
285:
282:
279:
276:
273:
250:
244:
238:
232:
229:
221:
217:
212:
210:
206:
202:
201:
196:
195:
190:
182:
177:
173:
169:
165:
158:
156:
154:
150:
146:
145:graph grammar
141:
139:
135:
131:
115:
95:
75:
69:
61:
56:
52:
50:
46:
42:
38:
34:
30:
26:
22:
1340:10.1142/4181
1330:
1311:10.1142/4180
1301:
1275:10.1142/3303
1265:
1224:
1220:
1197:
1186:
1164:
1153:, retrieved
1149:the original
1133:
1107:
1090:
1078:
1043:Graph theory
962:Soley Studio
764:
724:
716:
704:
699:
693:
671:
669:
659:
657:
652:
649:
608:
602:
431:
395:
391:
348:
344:
337:
334:gluing graph
333:
329:
213:
208:
204:
198:
192:
186:
175:
172:optimization
167:
148:
144:
142:
57:
53:
28:
24:
18:
1266:Foundations
1113:"TERMGRAPH"
1002:hypergraphs
714:and rings.
672:determinate
345:application
1244:10630/6716
1169:VDM Verlag
1155:2012-07-11
1144:9810228848
1083:Perez 2009
1065:References
1012:link parse
948:GraphSynth
696:term graph
349:host graph
143:Sometimes
1253:0304-3975
1070:Citations
827:Verigraph
811:GrGen.NET
628:→
622::
415:→
409::
375:→
369::
339:rewriting
330:invariant
326:injective
309:→
283:⊆
277:⊇
248:→
242:←
216:morphisms
73:→
60:rewriting
43:and also
1362:Category
1205:Archived
1037:See also
964:, is an
863:Archived
793:Archived
357:morphism
298:, where
207:and the
197:and the
1124:Sources
1014:into a
998:OpenCog
931:PROGRES
909:Henshin
899:Gremlin
850:eMoflon
831:Haskell
737:or the
645:pushout
353:pushout
176:Bottom:
88:, with
1346:
1317:
1281:
1251:
1175:
1141:
937:VIATRA
923:, and
881:Fujaba
821:GROOVE
540:where
396:double
1099:(PDF)
1008:RelEx
987:Kappa
893:GReAT
860:EMorF
676:logic
476:(see
433:match
47:) to
33:graph
27:, or
1344:ISBN
1315:ISBN
1279:ISBN
1249:ISSN
1173:ISBN
1139:ISBN
1026:The
790:GMTE
784:GP 2
778:Java
752:and
678:and
607:and
341:step
336:. A
168:Top:
1336:doi
1307:doi
1271:doi
1239:hdl
1229:doi
1225:412
952:XML
913:EMF
871:EMF
844:MDA
805:C++
774:AGG
343:or
324:is
19:In
1364::
1342:.
1313:.
1277:.
1247:.
1237:.
1223:.
1219:.
1200:.
1189:.
1171:,
1167:,
956:C#
919:,
905:).
833:).
815:C#
780:).
748:,
662:.
600:.
211:.
23:,
1352:.
1338::
1323:.
1309::
1287:.
1273::
1255:.
1241::
1231::
1182:.
1159:.
1115:.
1101:.
1018:.
958:.
939:.
927:.
895:.
877:.
807:.
756:.
631:R
625:L
619:r
588:G
568:K
548:K
528:G
508:R
488:L
464:G
444:L
418:G
412:L
406:m
378:D
372:K
366:k
312:L
306:K
286:R
280:K
274:L
254:)
251:R
245:K
239:L
236:(
233:=
230:r
116:R
96:L
76:R
70:L
39:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
