Multi-Hypergraph Grammar

S. Therasa1 and T. Rajaretnam2

1Department of Mathematics, University College of Engineering, Tiruchirappalli – (BIT CAMPUS) Anna University - 620024, Tamil Nadu, INDIA.
2PG & Research Department of Mathematics, St. Joseph's College (Autonomous), Tiruchirappalli – 620018, Tamil Nadu, India.

(Received on: September 20, 2017)


This study deals with the concept of hypergraph grammar which results in multi-hypergraph language. Few examples have been illustrated for regular multi-hypergraphs. The necessary condition for the two given multi-hypergraphs to be isomorphic is discussed. An example is given for the case that the condition is not sufficient.

Keywords: Hypergraph grammar, regular multihypergraph, regular multi‐hypergraph language.


Graphs are frequently used in various fields of Computer Science and Artificial Intelligence for representing knowledge of complex structures. This study deals with the concept of hypergraph grammar which is similar to string generating grammar whereas it generates multi-hypergraph instead of words. Hypergraph grammar provides a rule based mechanisms for generating, manipulating and analysing the graphs4. D. Caucal focused on providing some of the basic tools to reason out the deterministic graph grammar and on structural study of their generated graphs1,2. It further suitably defines that hypergraph grammar R = (G0, P) is an ordered pair where G0 is an initial graph and P is a set of collection of rules of the form X -> H or H -> H'. Here X is a hyperarc, H and H' are the multi - hypergraphs respectively. It also concerns that the rules of the grammar are deterministic and context free. Deterministic means that there is only one rule for every non‐terminal. It also discusses about regular multi-hypergraph of a given grammar and the languages generated by the grammar too. It proves the necessary condition for the two given multi-hypergraphs to be isomorphic and gives an example for that the condition need not be sufficient.


In this section, we have reviewed some fundamental concepts related to hypergraph grammar.

if the terminals are of arity 1 or 2. For any rule 𝑅1 of the grammar R, R(𝑅1) and R(𝑅1) depicts the left and the right hand side of the rule 𝑅1 respectively.


In this section, we define hypergraph grammar suitably and propose two methods in the derivation of the hypergraph grammar 𝑅.



The author has discussed the concept of hypergraph grammar and the languages recognized the grammar with suitable examples. The study has proved the necessary condition for the two multi-hypergraphs to be isomorphic. An example has been given for the condition is not sufficient.


  1. 1. D. Caucal, Handbook of Deterministic Graph Grammars, University of Paris-Est.
  2. D. Caucal, On the regular structure of prefix rewriting, 15th CAAP, LNCS 431, A. Arnold (Ed.), 87–102 (1990), and in Theoretical Computer Science 106, 61-86 (1992).
  3. Frank Harary, Graph Thoery, Narosa /Addison Wesley, Indian Student Edition, (1988).
  4. G. Rozenberg, editor. Handbook of Graph Grammars and Computing by Graph Transformation, Volume 1-3: Foundations. World Scientific, (1997).
map1 map2 map3