A study on two-dimensional grammars based on grammar systems and P-Systems

Abstract

In this thesis the two-dimensional grammars, namely, the basic puzzle grammars [33] and the matrix grammars [22] are studied in the context of Grammar systems and P systems and the generative power and other properties are examined. The thesis is divided into six chapters of which the first chapter forms the introduction giving the necessary background details. Chapters 2 to 6 develop various picture generating systems basically utilizing the concepts of grammar systems and P systems. A brief chapter-wise description of the work done is now presented and a detailed discussion is done in the respective chapters. Motivated by the study of cooperating array grammar systems [4], the power of cooperation in generating pictures is examined in Chapter 2, by taking basic puzzle grammars in the components of cooperating array grammar systems. The resulting system is called cooperating basic puzzle grammar system and the generative power of this system in the maximal derivation mode is brought out. In Chapter 3, the array-rewriting P systems of [1] are considered but the rules in the regions are again taken to be basic puzzle grammar [33] rules. The resulting system is called a BPG P System. The array handling power of this system is studied in this chapter. In Chapter 4, the rectangular array generating two-dimensional matrix grammars [22] are taken in the regions of an array P system giving rise to another variation of array P system, called sequential/parallel array P system.