[Executive Summary of the Report of the Minor Research Project Submitted to the University Grants Commission, South West Regional Office, Bangalore

by Smt. Ann Susa Thomas, Asst. Professor, Department of Mathematics St. Thomas College, Kozhencherry-689641 ]

EXTENSION OF COLLAGE GRAMMAR TO CELL WORKS

Smt. Ann Susa Thomas

UGC APPROVAL LETTER No. & DATE 1899- MRP/ 14-15/ KLMG022/ UGC-SWRO, 04-FEB-15 |

Images or pictures made of symbols constitute an important aspect of human life as humans can remember pictures better than words. Informally, a two-dimensional string is called a picture and is defined as an array of symbols. A two-dimensional language (or picture language) is a set of pictures. Graph grammar is a visual language with a set of valid visual sentences that are represented by some graphs. Graph grammars was introduced by A Rosenfeld as a formulation of some problems in pattern recognition and image processing. Graph grammar is similar to a string grammar in the sense that the grammar consists of finite sets of labels for nodes and edges, an axiom and a finite set of productions. Each production shows how a resulting graph can be derived from the previous one by a rewrite step. The topic of interest in the project is collage grammar which is a graph grammar and its extension to cell works.

From the early stage of development of 'formal language theory', picture languages have attracted the attention of researchers who tried to give interesting frameworks for generating two and higher dimensional pictures such as arrays, trees, graphs etc. Syntactic methods that give rise to models for image or picture generation have been motivated by various problems that arise in the framework of pattern recognition and image processing and by different applications such as character recognition, pictorial information system design, and so on. Collage grammars are studied as devices that generate pictures by rewriting based on hyperedge replacement. Informally, a collage consists of a set of geometrical parts, a sequence of pin points, and a set of hyperedges each coming with a nonterminal label and a sequence of attachment points. It specifies a picture by the overlay of all its parts. A hyperedge can be replaced by a collage if its pin points meet the attachment points. The hyperedges in decorated colleges serve as place holders for (decorated) collages and the key construction for generating collages is the replacement of hyperedges.

In order to capture the structure of three dimensional cellular tissues, Lindenmayer proposed an extension of Map L-systems called cell-work L-systems. A cell-work with fins in which each cell of a cell-work may divide into infinitely many cells at any instant of time was introduced by Robinson et al. Motivated by cell division patterns, that is, the spatial and temporal organization of cell divisions in tissues the main work of the project is the study of how three-dimensional cell works may be captured by context free, ET0L and part sensitive collage grammars. Depending on the production rules cell division pattern varies. This study can be realized by implementing algorithmic generation of such patterns leading to computer generated images.