RECORD
A Foundation for Functional Graph Programs: The Graph Transformation Control Algebra (GTA)
Software Engineering · Submitted 22 Dec 2022
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In this paper, we propose the "Graph Transformation control Algebra" (GTA) as such a foundation.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Applications of graph transformation (GT) systems often require control structures that can be used to direct GT processes. Most existing GT tools follow a stateful computational model, where a single graph is repeatedly modified "in-place" when GT rules are applied. The implementation of control structures in such tools is not trivial. Common challenges include dealing with the non-determinism inherent to rule application and transactional constraints when executing compositions of GTs, in particular atomicity and isolation. The complexity of associated transaction mechanisms and rule application search algorithms (e.g., backtracking) complicates the definition of a formal foundation for these control structures. Compared to these stateful approaches, functional graph rewriting presents a simpler (stateless) computational model, which simplifies the definition of a formal basis for (functional) GT control structures. In this paper, we propose the "Graph Transformation control Algebra" (GTA) as such a foundation. The GTA has been used as the formal basis for implementing the control structures in the (functional) GT tool "GrapeVine".
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Applications of graph transformation (GT) systems often require control structures that can be used to direct GT processes. | background 1.00 | 0.05 | 0.02 | asserted 0.95 |
| s1 | Most existing GT tools follow a stateful computational model, where a single graph is repeatedly modified "in-place" when GT rules are applied. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s2 | The implementation of control structures in such tools is not trivial. | background 0.94 | 0.05 | 0.02 | asserted 1.00 |
| s3 | Common challenges include dealing with the non-determinism inherent to rule application and transactional constraints when executing compositions of GTs, in particular atomicity and isolation. | background 0.98 | 0.07 | 0.02 | asserted 1.00 |
| s4 | The complexity of associated transaction mechanisms and rule application search algorithms (e.g., backtracking) complicates the definition of a formal foundation for these control structures. | background 0.91 | 0.07 | 0.02 | asserted 1.00 |
| s5 | Compared to these stateful approaches, functional graph rewriting presents a simpler (stateless) computational model, which simplifies the definition of a formal basis for (functional) GT control structures. | background 0.85 | 0.18 | 0.11 | asserted 1.00 |
| s6 | In this paper, we propose the "Graph Transformation control Algebra" (GTA) as such a foundation. | contribution 1.00 | 0.92 | 0.64 | asserted 1.00 |
| s7 | The GTA has been used as the formal basis for implementing the control structures in the (functional) GT tool "GrapeVine". | contribution 0.56 | 0.82 | 0.18 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Applications of graph transformation (GT) systems often require control structures that can be used to direct GT processes. Most existing GT tools follow a stateful computational model, where a single graph is repeatedly modified "in-place" when GT rules are applied. The implementation of control structures in such tools is not trivial. Common challenges include dealing with the non-determinism inherent to rule application and transactional constraints when executing compositions of GTs, in particular atomicity and isolation. The complexity of associated transaction mechanisms and rule application search algorithms (e.g., backtracking) complicates the definition of a formal foundation for these control structures. Compared to these stateful approaches, functional graph rewriting presents a simpler (stateless) computational model, which simplifies the definition of a formal basis for (functional) GT control structures. In this paper, we propose the "Graph Transformation control Algebra" (GTA) as such a foundation. The GTA has been used as the formal basis for implementing the control structures in the (functional) GT tool "GrapeVine".
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.