Formal Graph Language Theory & Fusion Grammars


In the first part of the presentation, some aspects of formal graph language theory are discussed. A few variants of graph grammars were introduced in the early 1970s as generalizations of Chomsky grammars. This first step into a formal graph language theory was further developed by the investigation of edge and hyperedge replacement on one hand and on some variants of node replacement on the other hand starting in the late 1970s. Since then, a good number of structural and decidability properties were proved. In particular, it turned out that hyperedge replacement grammars behave to a large degree in a context-free manner. In the second part of the presentation, the novel approach of fusion grammars is surveyed.

A fusion grammar is a hypergraph grammar which provides a start hypergraph of small connected components. To derive hypergraphs, connected components can be copied multiple times and can be fused by the application of fusion rules (where such an application removes two complementary hyperedges and merges their attachment vertices). The generated hypergraph language contains all terminal connected components of derived hypergraphs. The main results for various kinds of fusion grammars concern their generative power.

Friday, March 26, 2021 15:00 Europe/Paris
GReTA seminar
Hans-Jörg Kreowski
Hans-Jörg Kreowski
Professor in Computer Science (emer.)

Head of the Graph Transformation Group
I am member of the Technologie-Zentrum Informatik TZI (Centre for Computing Technologies) as a member of the TZI branch Software analysis and transformation SAT and a partner in the interdisciplinary Bremen Research Cluster for Dynamics in Logistics LogDynamics.

Aaron Frederick Lye
Aaron Frederick Lye
PhD student

I am currently a Ph.D. student in the Graph Transformation Group headed by Prof. Dr. Hans-Jörg Kreowski at the University of Bremen (Germany). Before, I was research assistant at the research group Combinatorial Algebraic Topology headed by Prof. Dr. Dmitry Feichtner-Kozlov and at the research group Computer Engineering/IT-Security headed by Prof. Dr. Tim Güneysu both also at the University of Bremen. While studying bachelor and master I was student research assistant in the research group Computer Architecture headed by Prof. Dr. Rolf Drechsler.