Rewriting Counts

In computer science, rewriting graphs (also rewriting graphs , transforming graphs , transforming graphs ) is a technique for creating a new graph from an original graph in an algorithmic manner. Rewriting graphs is widely used in computer science, for example, in software design , in software verification , in image generation, in compilers , in graph databases .

Graph transformations can be used as an abstraction of computations. The main idea is that the calculation state can be represented as a graph, the further steps of this calculation can be represented as transformation rules on this graph. Such rules consist of the original graph, which must be mapped to the full state subgraph, and a replacement graph, which will replace the mapped subgraph.

Formally, a graph rewriting system usually consists of a set of graph rewriting rules $L\rightarrow R$ ${\ displaystyle L \ rightarrow R}$ ${\ displaystyle L \ rightarrow R}$ where $L$ ${\ displaystyle L}$ $L$ called the reference graph (or left side), and $R$ ${\ displaystyle R}$ $R$ called the replacement graph (or the right side of the rule). The rule of rewriting a graph is applied to the original graph by searching for the occurrence of the template graph ( matching with the pattern , thereby solving the problem of isomorphism of the subgraph ) and replacing the found occurrence with an instance of the replacement graph. The rewriting rules can be further ordered in the case of labeled graphs , for example, in graph grammars controlled by rows.

Sometimes the concept of graph grammar is used as a synonym for a graph rewriting system, especially in the context of formal languages ; various formulations are used to emphasize the purpose of constructions, such as listing all graphs from some initial graph, that is, generating a graph language - instead of simply converting the initial state (host graph) to a new state.

Content

Graph rewriting approaches

Algebraic Approach

The algebraic approach to rewriting graphs is based on category theory . The algebraic approach is divided into sub-approaches, the most common of which are the double-pushout (DPO) and single-pushout (SPO) approaches. Other approaches include sesqui-pushout and pullback .

From the point of view of the DPO approach, the rule of rewriting a graph is a pair of morphisms in the category of graphs and graph homomorphisms between them: $r=(L\leftarrow K\rightarrow R)$ ${\ displaystyle r = (L \ leftarrow K \ rightarrow R)}$ (or $L\supseteq K\subseteq R$ ${\ displaystyle L \ supseteq K \ subseteq R}$ ), where $K\rightarrow L$ ${\ displaystyle K \ rightarrow L}$ injectively . Graph $K$ ${\ displaystyle K}$ called an invariant or sometimes gluing graph . Rewrite step or rule application $r$ ${\ displaystyle r}$ to source graph $G$ ${\ displaystyle G}$ defined by two diagrams of a codecart square , both leading to the same morphism $k\colon K\rightarrow D$ ${\ displaystyle k \ colon K \ rightarrow D}$ where $D$ ${\ displaystyle D}$ this is a context graph (where the name double- pushout comes from). Another graph morphism $m\colon L\rightarrow G$ ${\ displaystyle m \ colon L \ rightarrow G}$ models entry $L$ ${\ displaystyle L}$ at $G$ ${\ displaystyle G}$ and is called matching . The practical understanding of this is that $L$ ${\ displaystyle L}$ is a subgraph that maps from $G$ ${\ displaystyle G}$ (see the problem of finding an isomorphic subgraph ), and after a match is found, $L$ ${\ displaystyle L}$ replaced by $R$ ${\ displaystyle R}$ in the original graph $G$ ${\ displaystyle G}$ where $K$ ${\ displaystyle K}$ serves as an interface containing nodes and edges that were saved when applying the rule. Graph $K$ ${\ displaystyle K}$ needed to attach a pattern matching its context: if it is empty, a match can only indicate the entire connected component of the graph $G$ ${\ displaystyle G}$ .

The rule for rewriting a graph in the SPO approach is the only morphism in the category of labeled multigraphs and partial mappings that preserve the structure of a multigraph: $r\colon L\rightarrow R$ ${\ displaystyle r \ colon L \ rightarrow R}$ . Thus, the rewriting step is determined by a single codecart square diagram. A practical understanding of this is similar to the DPO approach. The difference is that there is no interface between the source graph $G$ ${\ displaystyle G}$ and count $G^{'}$ ${\ displaystyle G '}$ resulting from the rewriting step.

From a practical point of view, the key difference between DPO and SPO is how they relate to the removal of nodes with adjacent edges, in particular, how they avoid such deletions from leaving hanging edges. The DPO approach deletes a node only when the rule determines the removal of all adjacent edges, as well (this condition for dangling can be checked for this comparison), while the SPO approach simply places adjacent edges, without requiring an explicit specification.

There is also another algebraic approach to rewriting graphs, based mainly on Boolean and matrix algebras , called matrix graph grammars . ^[1] ^[2]

Deterministic Rewriting of Graphs

Another approach to rewriting graphs, known as determinate rewriting of graphs, has emerged from logic and database theory . 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 obtain unique results ( up to isomorphism), and this is achieved by applying any rewriting rule simultaneously throughout the graph, wherever it is applied, so that the result is really uniquely defined.

Rewriting an abstract semantic graph

Another approach to rewriting graphs is to rewrite an abstract semantic graph (ASG) , which involves processing or transforming an ASG through a set of syntax rewriting rules.

Abstract semantic graphs are an important issue in the study of programming languages, since the rules of rewriting the ASG are able to formally express the operational semantics of the compiler. ASGs are also used as an adaptation of an abstract machine for modeling chemical and biological calculations, as well as graphic calculations, such as parallel models. ASG can carry out automatic verification (verification) and logical programming, as they are well suited to the presentation of quantitative statements in first-order logic. Symbolic programming software is another LAS application that is able to represent and perform calculations with abstract algebraic structures such as groups, fields, and rings.

The TERMGRAPH conference ^[3] fully focuses on research in the field of LHG and their applications.

Graph grammar classes and graph rewriting systems

Graph rewriting systems, of course, are grouped into classes depending on the types of graph representations used and how the rewrites are expressed. The grammar of an abstract semantic graph, otherwise equivalent to a graph rewriting system or graph replacement system, is most often used in classifications. Some common types are:

Attribute graph grammars are typically formalized using the single-pushout approach or the double-pushout approach to characterizing the replacements mentioned in the previous section on the algebraic approach to rewriting graphs.
Hypergraph grammars, including more rigorous subclasses of port graph grammars, linear graph grammars, and interacting networks.

Implementations and Applications

Graph rewrite rule example (optimization from compiler construction: multiplication by 2 is replaced by addition)

Graphs are an expressive, visually and mathematically accurate formalism for modeling objects (subjects) connected by relationships; objects are represented as nodes, and the relationships between them are edges. Nodes and edges are typically typed and attributed. Computations are described in this model as changes in relations between subjects or as changes in the attributes of graph elements. They are encoded in the rules for rewriting graphs or transforming graphs and are executed using graph rewriting / graph conversion tools.

Application-neutral tools:
- AGG , Attribute Graph Grammar System ( Java ).
- GP (Graph Programs) , a programming language for computing on graphs with the direct application of graph conversion rules.
- GMTE (Graph Matching and Transformation Engine) engine for mapping and transforming graphs. It is an implementation of the extension of the Messmer algorithm in C ++ .
- GrGen.NET (Graph rewrite Generator), a graph conversion tool with code generation in C # or .NET assemblies.
- GROOVE , a set of tools in Java for editing graphs and graph transformation rules, for exploring state spaces of graph grammars and checking models of these state spaces; can also be used as a graph conversion engine.
- Verigraph , a software specification and verification system based on rewriting graphs ( Haskell ).
Tools for solving software development problems (mainly within the framework of a model-driven architecture (MDA) ) using graph rewriting:
- eMoflon , EMF compatible model conversion tool with Story-Driven Modeling and triple graph grammar support
- EMorF An EMF- based graph rewriting system that supports in-place and model-to-model conversions.
- Fujaba uses plot-driven modeling, graph rewriting language based on PROGRES
- Graph databases often support dynamic rewrite of graphs.
- Great
- Gremlin , a graphing programming language
- Henshin , an EMF- based graph rewriting system that supports in-place and model-to-model transformations, critical pair analysis and model validation
- PROGRES (PROgrammed Graph REwriting Systems) , an integrated environment and a very high-level language for programmable graph rewriting systems.
- VIATRA

Tools for mechanical engineering:
- GraphSynth is an interpreter and user language environment for creating unlimited graph grammars, as well as testing and finding the resultant. GraphSynth saves graphs and graph grammar rules into XML files and is written in C # .
- Soley Studio is an integrated development environment for graph transformation systems. Its main application focuses on data analysis in the field of engineering.
Biological Applications:
- Functional and structural modeling of plants using the language of the grammar graph
- Modeling multicellular development using string-regular graph grammar
Artificial intelligence, natural language processing:
- OpenCog provides basic pattern matching support (based on hypergraphs ), which is used to implement various AI algorithms.
- RelEx is an English parser that uses rewriting of graphs to convert link parsing to parsing .

Notes

↑ Perez, 2009 covers this approach in detail.
↑ This topic is expanded at mat2gra.info .
↑ TERMGRAPH (neopr.) .

References

Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations , World Scientific Publishing, volumes 1-3, ISBN 9810228848 , < http://www.informatik.uni-trier.de/~ley/db/conf /gg/handbook1997.html > .
Perez, PP (2009), Matrix Graph Grammars: An Algebraic Approach to Graph Dynamics , VDM Verlag , ISBN 978-3-639-21255-6 .
Haeckel, R. (2006). Convert graphs in a nutshell . Electronic Notes in Theoretical Computer Science 148 (1 specifications. ISS.), PP. 187-198.
König, Barbara (2004). Analysis and verification of dynamically changing systems . Doctoral dissertation, University of Stuttgart , PP. 65-180.
Lobo, Daniel. Graph grammars with string-regulated rewriting (Eng.) // Theoretical Computer Science . - 2011 .-- 1 October ( vol. 412 , no. 43 ). - P. 6101-6111 . - ISSN 0304-3975 . - DOI : 10.1016 / j.tcs.2011.07.07.004 .

[1] Perez, 2009 covers this approach in detail.

[2] This topic is expanded at mat2gra.info .

[3] TERMGRAPH (neopr.) .