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.
email:thema.jeje@gmail.com t_rajaretnam@yahoo.com.

(Received on: September 20, 2017)

ABSTRACT

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.

1.INTRODUCTION

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.

2. BASIC DEFINITIONS

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.

2.1 DERIVATION

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




4. NECESSARY CONDITION FOR TWO MULTI-HYPERGRAPHS TO BE ISOMORPHIC





5. CONCLUSION

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.

REFERENCES

  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