ABSTRACT
In this thesis, basic ingredients of partially ordered multisets were employed in which some of its formalisms were further developed and a set of rules formulated which explicitly characterize the chemical and physical functions, among others, of the processes taking place in a biological cell. In the sequel, a grid form of the Jouannaud-Lescanne set-based and submultiset-based multiset orderings have been developed. Relatively, more applicable definitions of the multiset orderings and some of their systematic relationships were presented. A possibility of extending the set-based multiset ordering to simple multisets of incomparable objects has also been observed. A consequence of partial ordering – a partial ordering which is restricted to incomparable element – was studied and a number of its examples presented. By using this concept, a variant of alternative P system using specialized rules was developed, and was shown to adequately simulate the activities of the biological cells as opposed to the conventional P systems whose rules represent the activities of the biological cells in an unspecialized manner. It is shown that with only one membrane and three rules, a nondeterministic alternative P system based on ideal ordering is able to characterize the family of recursively enumerable languages. Finally, some deterministic P systems based on weak rule priority were defined to carry out arithmetic operations and exemplified.
viii
TABLE OF CONTENTS
Title Page ————————————————————————————————– i
Declaration ———————————————————————————————— ii
Certification ———————————————————————————————- iii
Dedication ———————————————————————————————— iv
Acknowledgment —————————————————————————————– v
Abstract ————————————————————————————————– vii
Table of Contents ————————————————————————————- viii
List of Figures —————————————————————————————– xiii
List of Tables —————————————————————————————— xiv
CHAPTER ONE: GENERAL INTRODUCTION————————————————1
1.0 Introduction ———————————————————————————— 1
1.1 Statement of the Problem ——————————————————————– 8
1.2 Justification ————————————————————————————- 8
1.3 Aim and Objectives ————————————————————————— 9
1.4 Methodology ———————————————————————————- 10
1.5 Organization ———————————————————————————– 10
CHAPTER TWO: LITERATURE REVIEW—————————————————-11
ix
CHAPTER THREE: FUNDAMENTALS OF MULTISET, ORDER RELATION FORMAL LANGUAGE THEORY AND P SYSTEM —————————————–21
3.0 Introduction ————————————————————————————21
3.1 Preliminaries of Multiset ——————————————————————– 22
3.2 Some Properties Holding for Multiset Operations ————————————-24
3.3 Some Basic Terminologies on Order Relations —————————————– 26
3.4 Elementary Formal Language Prerequisites ——————————————– 32
3.4.1 Strings and languages ————————————————————————– 32
3.4.2 Operations with strings and languages ——————————————————-33
3.5 Chomsky Grammars ————————————————————————–36
3.6 Some Elements of Computability ———————————————————-38
3.6.1 Automata —————————————————————————————- 38
3.6.2 Register machine ——————————————————————————- 40
3.6.3 Turing machine ———————————————————————————-42
3.7 Membrane Systems —————————————————————————45
CHAPTER FOUR: PARTIALLY ORDERED MULTISETS FOR THE PROPOSED ALTERNATIVE P SYSTEM ———————————————————————– 59
4.0 Introduction————————————————————————————-59
4.1 The Concept of Set-based Grid of a Partially Ordered Multiset———————60
4.1.1 Set-based difference grid———————————————————————–65
x
4.1.2 Grid approach to Jouannaud-Lescanne‟s set-based multiset ordering ——————-69
4.2 Redefined Submultiset-based Multiset Ordering via Grid —————————73
4.2.1 The concept of submultiset-based grid of a partially ordered multiset ——————74
4.2.2 Submultiset-based difference grid ———————————————————– 79
4.2.3 Grid approach to the Jouannaud-Lescanne‟s submultiset-based multiset ordering —-81
4.3 Some Results Holding for Multiset Ordering ——————————————–84
4.4 Some Extensions of Set-based Ordering to Simple Multisets of Incomparable Objects——————————————————————————————–90
4.5 The Concept of „Ideal‟ Ordering ———————————————————–96
4.5.1 Ideal ordering (a consequence of the properties of partial ordering) ——————–96
4.5.2 The structure of an isosceles triple ———————————————————– 98
4.5.3 Examples of ideal ordering/set ————————————————————– 101
4.5.4 The structure of an ideal set —————————————————————– 105
CHAPTER FIVE: AN APPLICATION OF IDEAL ORDERING TO ALTERNATIVE P SYSTEMS ——————————————————————————————— 107
5.0 Introduction ———————————————————————————- 107
5.1 A Biochemical Interpretation of the Rules ——————————————— 109
5.1.1 Mixture —————————————————————————————–109
5.1.2 Null reaction ———————————————————————————–110
5.1.3 Reversible chemical reaction —————————————————————-111
xi
5.1.4 Catalytic reaction —————————————————————————– 111
5.1.5 Physical change ——————————————————————————- 111
5.1.6 Incomparability with respect to reaction —————————————————112
5.1.7 An approach for non-determinism———————————————————–112
5.1.8 Derived reactions —————————————————————————– 112
5.2 Turing Computability ———————————————————————–114
5.3 A Nondeterministic Alternative P System with Specialization Rules Based on Ideal Ordering ——————————————————————————–115
5.4 The Computational Power of Cooperative Alternative P System with Specialization Rules in One Membrane based on Ideal Ordering —————- 117
5.5 Some Applications of P Systems to Arithmetic Operations on Non-negative Integers – a Case of Determinism Based on Weak Rule Priority ——————119
5.5.1 Weak versus strong rule priority relations ————————————————-119
5.5.2 Addition P system —————————————————————————- 121
5.5.3 Subtraction P system ————————————————————————- 122
5.5.4 Multiplication P system ———————————————————————-123
5.5.5 Multiplication P system exemplified ——————————————————-125
5.5.6 Division P system —————————————————————————- 129
5.5.7 Division P system exemplified ————————————————————–132
CHAPTER SIX: SUMMARY CONCLUSION AND RECOMMENDATIONS———138
xii
6.0 Summary ————————————————————————————–138
6.1 Conclusion————————————————————————————–139
6.2 Recommendations for future research ————————————————–140
INDEX OF RESULTS OBTAINED ————————————————————–142
REFERENCES —————————————————————————————-144
CHAPTER ONE
GENERAL INTRODUCTION
CHAPTER ONE: GENERAL INTRODUCTION
1.0 Introduction
P system is a computational device which is designed to model biologically inspired processes. It abstracts the way in which chemicals interact or cells behave. The device was first submitted as a report in Păun (1998) and subsequently published in Păun (2000), and hence the name. Although inspired by biology, the primary research interest in P systems is concerned with their use as a computational model rather than for biological modelling (Păun & Rozenberg, 2002) although this is also being investigated (Păun, 2006, Ardelean and Cavaliere, 2003).
It is worth mentioning some of the basic features of models investigated in P system. The compartments of a cell contains molecules and other substances swimming in an aqueous solution. Thus, the suggestion is to work with objects whose multiplicities matter, hence with multisets. This is a data structure with peculiar characteristics, not new but not exhaustively investigated in Mathematics and applied in Computer Science.
Also of interest in our research is the notion of multiset ordering. We redefine the Jouannaud-Lascanne‟s mulitset ordering based on the concept of grid. To this end, we define the concepts of grid, difference grid and grid-based orderings. We extend
2
the set-based multiset ordering to accommodate simple multisets of incomparable objects which are a systematic way of proving that the grid-based ordering is stronger than the conventional set-based ordering. Also, we consider the concept of ideal ordering – a partial ordering whose property is restricted to the partially ordered relation and the accompanying incomparability relation on three elements. The main idea behind the use of ordering in the model of P system is to introduce the rule representing the so-called derived reaction. This rule together with those representing physical change, chemical reaction, catalytic reaction and mixture are responsible for the evolution of the variant of P system introduced.
We apply the concept of P system to arithmetic operations on non-negative integers. The P systems obtained are of deterministic type based on the weak priorities for rule application. It is verified that two membranes suffice. Moreover, there are at most four objects for multiplication and five objects for division throughout the computation processes. The P systems so obtained serve as bases upon which other complex operations may be built, and upon which basic operations may be extended to cover the set of positive and negative real numbers.
It may be noted that many other natural computing devices have been in existence, namely, neural networks, (Bishop, 1995), genetic algorithm, (Davis, 1991) and DNA computing (Păun et al., 1998). None of these areas considers the cell itself as its object of research, and pays attention to the structural properties of membranes and compartmentalization. Moreover, nature computes not only at the
3
neural or genetic or molecular level, but also at the cellular level (Păun, 2006). This is what membrane computing is concerned about. Since the primary research interest in P systems is concerned with their use as a computational model the area of study can be seen as an extension of DNA computing (or more generally, molecular computing) from the one processor level to a distributed computing model.
P system is one of the most widely researched areas in the line of emerging computing devices inspired by natural biological phenomena. Essentially, the study of the cell cannot be understood without considering membranes. As a matter of fact, parts of a biological system are delimited by membranes. It begins with the membranes which enclose the internal organs of the cell – the nucleus, the Golgi apparatus, etc, and the outermost membrane covering a cell, also called the skin membrane. It goes a long way to the skin of an individual organism which separates the organism from the environment. There is also the concept of a virtual membrane which delimits, for example, a part of an ecosystem. This gives the flavor of distributed computing to this model. There are different but well delimited computing units that coexist and are hierarchically arranged in a complex system, from a single processor level to the World Wide Web. Such distributed symbol processing systems are mirrored in mathematical terms by exploiting a grammar system and multiset and its associated algebra, automata systems and register machines.
Since the biological membranes are known to be semi-permeable, membranes prevent certain chemicals and allow other chemicals to pass through it in a selective
4
manner. Sometimes the movement is only in one direction, and sometimes it is bi-directional. This can be a simple selection by size, in the case of small molecules, or a much more non-trivial selection, through protein channels, which not only select, but can also pass molecules from a region of low concentration to a region of higher concentration and vice versa, probably coupling molecules as they move, in a process called symport or antiport. Of course, variants could be developed in which the system has so-called opaque membranes, opaque in the sense that no movement across such membranes is allowed. It may be natural that this variant is rarely studied. An important role of membranes in membrane computing is that each membrane is seen as a separator of two regions, the region inside the membrane and the region outside the membrane.
A basic ingredient of membrane computing is the notion of membrane structure. It is a hierarchical architecture composed of non-intersecting membranes placed inside a unique membrane called the skin membrane. Non-intersecting in the sense that the arrangement of two membranes is either that one contains the other or they are disjoint. Such architecture is usually represented by a Venn diagram for simplicity. However, formal definition of a membrane structure exists.
Next, we consider the notion of a super-cell system. A super-cell system is a membrane structure with objects placed in the regions delimited by the membranes. Several copies of a particular object can appear. This gives rise to the use of multisets, which simply are sets whose elements can have multiplicities associated with them.
5
A P system is a super-cell which has the ability to evolve. In other words, a P system is a membrane structure with objects in some of the regions specified by the membranes, with specified evolution rules for the regions and input and output membranes. The rules in these regions are responsible for the evolution of the objects. The P system pre-specifies input and output membranes. The input and output membranes contain respectively, the input objects before a computation and the output objects after the computation. Any object, alone or together with one more object, can evolve – be transformed into other objects, be passed from one region to the other through a membrane, and can dissolve the membrane into which it is placed. All objects can evolve at the same time, in parallel. In other words if a rule is applied to a particular object, it should be applied as much as possible to the copies of the object in the membrane containing such rule. Moreover, all membranes are active at the same time. That is, all the membranes in the system work in parallel. It can be therefore seen that there exists two levels of parallelism in membrane computing.
A computation in a membrane system is obtained by starting with an initial state called initial configuration. Objects are placed in the input membrane. Such objects define the input for the computation. Rules are then applied in a maximally parallel manner to the objects placed inside the regions delimited by the membranes, non-deterministically choosing the rules. This is done in parallel for all the membranes whose rules can be applied at that moment. A computation halts when no
6
rules can further be applied in the system. The output of the computation is obtained by the number and multiplicity of the objects inside a predefined output membrane.
The rules which make the objects in these membranes to evolve may be given priorities as to which to be applied first and which to be applied next and so on. Also rules which have no priorities assigned to them are chosen non-deterministically. The system is said to be cooperative if there are rules which specify the evolution of several objects at the same time and non-cooperative if all the rules specify that only one object evolve at the same time. An intermediate case is where there are certain objects called catalysts which do not evolve alone, but help in the evolution of other objects, and are not modified by the rules. We call the systems of the type so far explained transition P systems as distinguished from other variants which are also considered in various texts.
It is worth mentioning that the cooperative P systems and systems with catalysts have computational completeness. That is, they can characterize the recursively enumerable sets of natural numbers. It is with this notion that the super-cell structure is used as a support for a computing device based on any type of objects and any type of evolution rules associated with them. In the above case, the objects are single symbols, taken from a set called an alphabet. Also considered is a case where the objects are strings. In this case an infinite set of objects can be used, which can evolve in many ways. Such ways are defined by rules which process strings. Rules such as insertion, deletion, rewriting, splicing and point mutation, just to
7
mention a few, have been used. Splicing is a technical term in molecular biology and genetics meaning the operation of modifying the nascent pre-messenger RNA transcript in which introns are removed and exons are joined.
It is worth mentioning that a P system is a computing device with input and output relation and pertains to natural computing. One is interested in an output given a particular input. P systems are universal in the sense that their computational ability can be compared to that of a Turing machine. Hence, we say that they are computationally complete. Interesting researches in membrane computing are already ongoing most of which lay emphases on the computational completeness, power and efficiency of its variants.
An element which is pre-requisite for researches in membrane computing is the theory of formal language. In fact, Kitano (2002) views membrane computing as a branch of formal language theory. It is worth mentioning that the proof techniques, the generative style, the rewriting-type of multiset processing rules are very much similar to formal language theory. As a result, most papers on P systems start by collecting a long list of notations and results from formal language theory. Basic regulations on the context-free grammars, such as matrix grammars (with appearance checking), are not only used, but are promisingly very powerful and raise new and interesting research questions. The use of matrix grammars is rather useful in many cases, because they involve contest-free grammars, which is the most widely investigated and applied class of Chomsky grammars and they have beautiful normal
8
forms and more importantly, they are very powerful results, proved decades ago. See Rozenberg and Salomaa (1997), Martin-Vide and Păun (2001) and Kitano (2002) for detailed reading. In particular, Kitano (2002) is handy for interested authors of membrane computing.
1.1 Statement of the Problem
Quasi-general P systems have been modelled strictly by means of rules which represent the processes taking place in a biological cell without explicitly specifying the biological, chemical or physical function of each rule as is obtainable in the said cell. It can therefore be said that the P systems have not been able to adequately simulate the activities of the biological cell, and thus cannot be said to truly carry out the computational capabilities of the cells in question. Bearing in mind such shortcomings, we intend to model an alternative P system, which is capable of simulating biological activities at cellular level and can compute all recursively enumerable sets of natural numbers with limited number of rules, each of which would function in a specialized manner.
1.2 Justification
P system is one of the most researched areas in the field of natural computing. However, the known variants of P systems basically make use of the application of rules to objects within regions and from one region to another without accounting for the biological functions (reactions) of each of the rules used. The variant of P system in this thesis considers physical change, chemical reaction, mixtures and derived
9
reaction among others. The variant of P system is therefore more realistic. Moreover, it uses the mathematical tool of multiset ordering, thereby rendering the variant of P system more elegant in its application. It uses limited number of rules and only one membrane to achieve computational completeness.
1.3 Aim and Objectives
The aim of this research is to develop an alternative P system based on an ideal consequence of partial ordering on multisets which would be capable of modelling biological systems.
The main objectives of this research are to:
i. Construct a grid-based multiset orderings and compare them with their existing partition-based counterparts.
ii. Investigate the possibility of extending the set-based multiset ordering to simple multisets of incomparable objects.
iii. Examine the concept of ideal ordering – a property restricted partial ordering on multisets, with examples.
iv. Construct a nondeterministic alternative P system.
v. Investigate the computational completeness of the proposed alternative P systems.
vi. Design algorithms to compute the four basic arithmetic operations in deterministic P systems based on the weak rule priority.
10
1.4 Methodology
A grid approach was used to redefine the set-based and submultiset-based orderings which was originally defined by Jouannaud and Lascanne. Also, we used the induction method of proof to show that the set-based ordering can be extended to simple multisets of incomparable objects. A multiset ordering approach was followed in conjunction with physical change, chemical reaction, derived reaction, mixture and the null reaction to model a process taking place in a living organism. Moreover, a register machine was used to prove that the model of P system presented is computationally complete. For the application of P system to arithmetic operations on non-negative integers, we used the method of weak rule priority to achieve determinism for the system.
1.5 Organization
This thesis is subdivided into six chapters. Chapter one gives a general introduction to the study. In Chapter Two, a comprehensive review of the literature of P systems and multiset orderings relevant to the research are presented. In Chapter Three, some of the fundamentals of P system and multiset orderings were observed. In particular, the concept of ideal ordering is introduced and some proposed results are investigated. In Chapter Four, a deterministic alternative P system based on the concept of ideal ordering is presented. In Chapter Five, we present the application of P systems in modelling arithmetic operations based on the weak rule priority. Chapter six contains conclusions and summary.
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
