Project Materials

A Study of the Application of Multi-Set to Membrane Computing

ABSTRACT

We present a Venn diagram model, a tree-based model and a multi-set based model for membrane structure and point out some of their limitations. We construct a multi-set based tree model of membrane structure to resolve some of the limitations mentioned earlier. We also construct a saw-like structure to embed into it the multi-set based tree model of membrane structure.

TABLE OF CONTENTS

Title Page — — — — — — — — — — — — — — — — i
Declaration — — — — — — — — — — — — — — — — ii
Certification — — — — — — — — — — — — — — — — iii
Dedication — — — — — — — — — — — — — — — — — — — iv
Acknowledgement — — — — — — — — — — — — — — v
Abstract — — — — — — — — — — — — — — — — vi
Table of Contents — — — — — — — — — — — — — — vii
List of Figures — — — — — — — — — — — — — — — xi
List of Tables — — — — — — — — — — — — — — — xii

CHAPTER ONE: GENERAL INTRODUCTION — — — — — — — — 1
1.1 Introduction — — — — — — — — — — — — — — — 1
1.2 Statement of the Problem — — — — — — — — — — — — 2
1.3 Research Motivation — — — — — — — — — — — — — 2
1.4 Objective of the Research — — — — — — — — — — — — 2
1.5 Organization of the Thesis — — — — — — — — — — — — 3
1.6 Methodology — — — — — — — — — — — — — — — 3

CHAPTER TWO: REVIEW OF LITERATURE — — — — — — — — — 4
2.1 Cell Biology — — — — — — — — — — — — — — — 4
2.2 Some History of the Development of Multi-sets — — — — — — — 5
2.3 Some Directions in Developing Membrane Computing — — — — — 9
8

CHAPTER THREE: FUNDAMENTALS OF MULTI-SET — — — — — — 13
3.1 Preliminaries — — — — — — — — — — — — — — — 13
3.2 Representation of Multi-sets — — — — — — — — — — — 14
3.2.1 Multiplicative Form — — — — — — — — — — — — — 14
3.2.2 Linear Form — — — — — — — — — — — — — — —14
3.2.3 Multi-set as a Sequence — — — — — — — — — — — — 15
3.2.4 Multi-set as a Family of Sets — — — — — — — — — — — 15
3.2.5 Multi-set as a Generalised Characteristic Function — — — — — — 16
3.3 Definition of Terms — — — — — — — — — — — — — 16
3.4 Properties of Multi-set Operations— — — — — — — — — — 27
3.5 Multi-set and the Termination of Programs— — — — — — — — 28
3.5.1 A Basis for Program Termination — — — — — — — — — —29
3.5.2 The Multi-set Ordering — — — — — — — — — — — — 29
3.5.3 The Nested Multi-set Ordering — — — — — — — — — — 30
3.5.4 Program Termination with Multi-set Ordering— — — — — — — 32
3.5.5 Counting Tips of Binary Trees — — — — — — — — — — 32
3.5.6 McCarthy’s 91 Function— — — — — — — — — — — — 34
3.5.7 Ackermann’s Function — — — — — — — — — — — — 36

CHAPTER FOUR: APPLICATION OF MULTI-SET TO MEMBRANE
COMPUTING — — — — — — — — — — — — — — — — 38
4.1 Introduction — — — — — — — — — — — — — — — 38
4.2 Membrane Structure: Some Conceptual Reflections — — — — — — 39
4.2.1 The Cell — — — — — — — — — — — — — — — — 39
9
4.2.2 The Biological Cell Membrane — — — — — — — — — — 41
4.2.3 Membrane Transportation — — — — — — — — — — 41
4.3 Membrane Computing — — — — — — — — — — — 45
4.4 Structure of Membrane Computing — — — — — — — — — 46
4.5 Basic Variants of P Systems — — — — — — — — — — 47
4.5.1 Transition P Systems — — — — — — — — — — — 47
4.5.2 P Systems with Active Membranes— — — — — — — — — 47
4.5.3 Tissue-like P Systems — — — — — — — — — — — 48
4.5.4 Neural-like P Systems — — — — — — — — — — — 48
4.6 Components of a P System — — — — — — — — — — 48
4.6.1 The Environment — — — — — — — — — — — — 48
4.6.2 Result of Computation — — — — — — — — — — — — 49
4.6.3 Membranes— — — — — — — — — — — — — — — 49
4.6.4 Catalysts — — — — — — — — — — — — — — — 49
4.6.5 Rules — — — — — — — — — — — — — — — 50
4.6.6 Computations — — — — — — — — — — — — — — 50
4.7 Aptness for Applying Multi-sets to Membranes— — — — — — — 50
4.8 The Structure of Membranes— — — — — — — — — — — 51
4.9 Rules of Evolution — — — — — — — — — — — — — 52
4.10 A Formal Definition of a Transition P System — — — — — — — 56
4.11 Defining Computations and Results of Computations — — — — — 58
4.12 Extending the Definition Given in Section 4.10 — — — — — — — 59
4.13 Using Symport and Antiport Rules — — — — — — — — — — 62
10
4.14 Super-cells — — — — — — — — — — — — — — — 65
4.15 Transition Super-cell Systems — — — — — — — — — — — 65
4.16 Computation and Result of Computation in a Transition Super-cell System — 66

CHAPTER FIVE: MULTI-SET BASED TREE STRUCTURES AND THEIR
APPLICATION TO MEMBRANE COMPUTING — — — — — — — — 71
5.1 Introduction — — — — — — — — — — — — — — 71
5.2 Some Application Areas — — — — — — — — — — — — 72
5.3 Aptness for the use of Trees and a Multi-set Environment — — — — — 73
5.4 Some Basic Concepts — — — — — — — — — — — — 74
5.5 The Binary Tree — — — — — — — — — — — — — — 75
5.6 Conventional Approach to Representing a Tree by a Well-founded Multi-set — 78
5.7 Well-founded Multi-set Representation of a Binary Tree — — — — — 79
5.8 The Saw Rule— — — — — — — — — — — — — — — 82
5.9 Representation of a Tree by a Saw-like Permutation of a Well-founded Multi-set
(the saw rule) — — — — — — — — — — — — — — — — 86
5.10 Tree Structure – based Representation of Membrane Structures — — — 95
5.11 Computation (An Example) — — — — — — — — — — — 98
5.12 Conclusion and Future Directions — — — — — — — — — — 101
REFERENCES — — — — — — — — — — — — — — — — 103

CHAPTER ONE

GENERAL INTRODUCTION

1.1 INTRODUCTION

A quasi-generally accepted schematic comprehension of a biological system can be described as a hierarchical structure in which deterministic or non-deterministic or stochastic (or random) interactions among its various substructures characterized by a set of basic components take place.

It is also presumed that the said interactions do take place cooperatively and competitively leading to an equilibrium (or emergent) or unstable or chaotic state.
Having the aforesaid orientation in mind, a biological system can be viewed as a multi-set object space that evolves by means of application of rewriting rules.

Thus, it seems plausible to construct a multi-set model to mimic the biological evolution, such as a P system or its variant – a transition P system. Essentially, the interactions between substructures of a bio-system can be mimicked by suitably formulated relations with bound multiplicities.

In the sequel, the rule based multi-set programming paradigm (Krishinamwithy, 2006) has been found of immense importance in the construction of algorithms for Deoxyribonucleic acid (DNA), (more generally, molecular) and membrane computing, augmenting programmable living machines, comprehending evolutionary processes. In the recent years, a good number of researches (Păun 2002, Rogozhin et al., 2004 and Amos 1997) have been undertaken in this direction.

It is difficult to trace the origin of multi-set. In the recent years, the notion of multi-set has been re-discovered, analyzed and employed in various areas of mathematics, computer science, linguistics and logic.
We will present a brief account of the application of multi-set in our literature review.

In
course of doing this, we will specify the main area of our research in this thesis vis-à-vis:
application of multi-set to membrane computing.

1.2 STATEMENT OF THE PROBLEM

We propose to study fundamentals of multi-set and membrane structure to formulate a multi-set based tree model for membrane computing.

1.3 RESEARCH MOTIVATION

Recently, the subject of membrane computing has become an important area of research. The application of multi-set in diverse fields, especially in membrane and molecular computing, motivated our study.

1.4 OBJECTIVE OF THE RESEARCH

The aim of this thesis is as follows:

i. We propose to present a critical study of the existing multi-set models for DNA and membrane computing.

ii. We propose to study membrane computing specifically by way of providing a multi-set based tree model.

iii. We also wish to outline constructions of multi-set based biological simulators.

1.5 ORGANISATION OF THE THESIS

The thesis consists of five chapters. In chapter one, a brief explanation of multi-set and biological systems, statement of the problem, research motivation, objective of the research and organization of the thesis are presented. In chapter 2, we present literature review.

In chapter 3, we present a brief account of fundamentals of multi-set with an emphasis on the termination of programs. In chapter 4, we present an overview of various directions the researches have been undertaken in the proposed area.

In chapter 5, we design a tree model of membrane structures for membrane computing. We raise some issues that have not been addressed as yet and finally outline construction of multi-set based biological models. The references of all cited works are presented.

1.6 METHODOLOGY

We study the existing models of membrane structure namely: Venn diagrammatic, tree-based, and multi-set based and identify some of their limitations. We construct a multi-set based tree model to resolve certain limitations mentioned earlier. We also construct a saw-like structure to embed in it our multi-set based tree model of membrane structure.