ABSTRACT
We present a Venn diagram model, a tree-based model and a multiset-based model for
membrane structure and point out some of their limitations. We construct a multisetbased
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 multiset-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 Organisation 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 Multisets — — — — — — — 5
2.3 Some Directions in Developing Membrane Computing — — — — — 9
8
CHAPTER THREE: FUNDAMENTALS OF MULTISET — — — — — — 13
3.1 Preliminaries — — — — — — — — — — — — — — — 13
3.2 Representation of Multisets — — — — — — — — — — — 14
3.2.1 Multiplicative Form — — — — — — — — — — — — — 14
3.2.2 Linear Form — — — — — — — — — — — — — — —14
3.2.3 Multiset as a Sequence — — — — — — — — — — — — 15
3.2.4 Multiset as a Family of Sets — — — — — — — — — — — 15
3.2.5 Multiset as a Generalised Characteristic Function — — — — — — 16
3.3 Definition of Terms — — — — — — — — — — — — — 16
3.4 Properties of Multiset Operations— — — — — — — — — — 27
3.5 Multiset and the Termination of Programs— — — — — — — — 28
3.5.1 A Basis for Program Termination — — — — — — — — — —29
3.5.2 The Multiset Ordering — — — — — — — — — — — — 29
3.5.3 The Nested Multiset Ordering — — — — — — — — — — 30
3.5.4 Program Termination with Multiset 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 MULTISET 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 Multisets 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: MULTISET–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 Multiset Environment — — — — — 73
5.4 Some Basic Concepts — — — — — — — — — — — — 74
5.5 The Binary Tree — — — — — — — — — — — — — — 75
5.6 Conventional Approach to Representing a Tree by a Wellfonded Multiset — 78
5.7 Wellfounded Multiset 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 Wellfounded Multiset
(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 multiset
object space that evolves by means of application of rewriting rules. Thus, it seems
plausible to construct a multiset 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 multiset 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.
14
It is difficult to trace the origin of multiset. In the recent years, the notion of multiset 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 multiset 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 multiset to membrane computing.
1.2 STATEMENT OF THE PROBLEM
We propose to study fundamentals of multiset and membrane structure to formulate a
multiset-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 multiset 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:
15
i. We propose to present a critical study of the existing multiset models for DNA and
membrane computing.
ii. We propose to study membrane computing specifically by way of providing a
multiset–based tree model.
iii. We also wish to outline constructions of multiset-based biological simulators.
1.5 ORGANISATION OF THE THESIS
The thesis consists of five chapters. In chapter one, a brief explanation of multiset 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 multiset 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 multisetbased
biological models. The references of all cited works are presented.
1.6 METHODOLOGY
We study the existing models of membrane structure namely: Venn diagrammatic, treebased,
and multiset-based and identify some of their limitations. We construct a multiset
based tree model to resolve certain limitations mentioned earlier. We also construct a
saw-like structure to embed in it our multiset-based tree model of membrane structure.
Do you need help? Talk to us right now: (+234) 08060082010, 08107932631 (Call/WhatsApp). Email: [email protected].
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
