In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, an attributed graph grammar is a class of
graph grammar
In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also ...
that associates vertices with a set of attributes and rewrites with functions on attributes. In the algebraic approach to graph grammars, they are usually formulated using the
double-pushout approach
In computer science, double pushout graph rewriting (or DPO graph rewriting) refers to a mathematical framework for graph rewriting. It was introduced as one of the first algebraic approaches to graph rewriting in the article "Graph-grammars: An al ...
or the
single-pushout approach
In computer science, a single pushout graph rewriting or SPO graph rewriting refers to a mathematical framework for graph rewriting, and is used in contrast to the double-pushout approach
In computer science, double pushout graph rewriting (or DPO ...
.
Implementation
AGG, a rule-based visual language that directly expresses attributed graph grammars using the single-pushout approach has been developed at
TU Berlin
The Technical University of Berlin (official name both in English and german: link=no, Technische Universität Berlin, also known as TU Berlin and Berlin Institute of Technology) is a public research university located in Berlin, Germany. It wa ...
for many years.
Notes
References
*{{citation, first=Grzegorz, last=Rozenberg, title=Handbook of Graph Grammars and Computing by Graph Transformations, publisher=World Scientific Publishing, volumes 1–3, year=1997, isbn=9810228848, url=http://www.informatik.uni-trier.de/~ley/db/conf/gg/handbook1997.html.
*Ehrig, Heckel, Korff, Lowe, Ribeiro, Wagner and Corradini, 1997. Algebraic Approaches to Graph Transformation - Part II: Single Pushout Approach and Comparison with Double Pushout Approach. Pp. 247-312 of (Rozenberg, 1997).
Graph rewriting