A Study of the Application of Multiset to Membrane Computing
Chapter One
OBJECTIVE OF THE RESEARCH
The aim of this thesis is as follows:
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.
CHAPTER TWO
REVIEW OF LITERATURE
In this chapter, we look at some of the various efforts in developing multiset and its application to mathematics, linguistics, statistics, computer science, membrane and molecular (or DNA) computing. Details of the study of some significant applications appear in chapter four; of particular interest being its application to membrane computing.
CELL BIOLOGY
Throughout time, thoughts and ideas of life have evolved, stretching from biogenesis and spontaneous generation to the modern cell theory. In 1824, Rene Dutrochet discovered that “the cell is the fundamental element in the structure of living bodies, forming both animals and plants through juxtaposition.” However, the first sightings of the internal
action of the cell were made by Robert Brown. Schwann created the term “cell theory” and declared that plants consisted of cells. This declaration was made after that of Mathias Schlieden (1804 – 1881) that animals are composed of cells and that living organisms are made up of basic microscopic units called cells. All cells fall into one of the two major classifications: prokaryotes and eukaryotes. The later is more complex and contains nuclear materials. Plants and animals are made of cells and that most of the cell organelles are considered identical, yet they do have their differences (Harrison, 1994).
SOME HISTORY OF THE DEVELOPMENT OF MULTISETS
The idea of having a repeated element in a set dates back to as far as numbers itself. For example, evidences of representing a number by a collection of tally marks or units are found in the work of the Babylonians in 200 B.C., Egyptians and Greek in 3500 – 1700 B.C. Knuth (1981) notes that enumeration of permutations of a set was known in ancient times and historically the first known document is the Hebrew Book of Creation in 100 A.D., followed by the Indian Classic Anuyogadvarā-sutra in 500 A.D.; and the corresponding result for multisets seems to have appeared first in another Indian Classic
He further notes that Kircher (C. 1650, pp. correctly gave the number of permutations of multiset {m.C, n.D} for several values of m and n. A generalization of the rule for enumerating the permutations of multiset appeared
in Prestet’s Elémens de mathématiques (Paris 1675, 351 – 352), and later in John Walli’s Treatise of Algebra 2 (Oxford 1685, pp. 117 – 118). By exploiting Dominique Floata’s work done in 1965, Knuth present a good number of significant results on multiset permutations (Singh, 2006).
CHAPTER THREE
FUNDAMENTALS OF MULTISET
In this chapter, we intend to explicate the meaning of multiset, show various ways in which a multiset can be represented. We define operations on multiset, submultisets, similar multisets, ordered pair of two multiset terms, power multists, union intersections and sum of multisets, difference and complementation of multisets and function between multisets. We show that Cantor’s theorem and Schröder–Bernstein’s theorem fail with multisets. Finally, we talk about the Darshowitz–Manna ordering on multisets.
PRELIMINARY
A multiset is a collection of elements in which repetition of elements is allowed. A set is a multiset in which distinct elements occur only once. The copies of an element in a multiset are called indistinguishables. The number of occurrences of an element in a multiset is called its multiplicity. The multiplicity of an element in a multiset contributes to the cardinality of the multiset. That is, the cardinality of a multiset is the sum of the multiplicities of the elements in the multiset. A multiset is finite if the distinct elements of the multiset are finite and every element has finite multiplicity. A multiset is therefore infinite if the distinct elements of the multiset are infinite or some elements have infinite multiplicities (Blizard, 1991).
CHAPTER FOUR
APPLICATION OF MULTISET TO MEMBRANE COMPUTING
In this chapter, we highlight some biological concepts as relating to cells and membrane structures, we demonstrate how multiset theory can be applied to membrane computing in particular and molecular (DNA computing) in general. Of interest is the representation of the evolving objects in a biological cell as a string of multiset of symbol objects.
INTRODUCTION
As reflected in the general introduction part of this thesis, as of last three decades or so, the mathematics of multisets has found applications in mathematics and computer science, besides logic, linguistics, physics, biology, economics, etc. Recently, a good number of its applications have been witnessed in DNA (or molecular) and membrane
computing.
A more recent branch of natural computing with an enthusiastic beginning and computational yet, unconfirmed applicability is DNA computing, whose birth is related to Adleman’s experiment of solving a small instance of the Hamiltonian path problem by handling DNA molecules in a laboratory. DNA structure and processing suggest a series of new data structures and operations that the massive parallelism made possible by the efficiency of DNA as a support of information promises to be useful in solving computationally hard problems in a feasible time.
CHAPTER FIVE
MULTISET–BASED TREE STRUCTURES AND THEIR
APPLICATION TO MEMBRANE COMPUTING
In this chapter, we explicate a new paradigm proposed for study – multiset-based tree structures and their applications, especially to membrane computing. We represent a tree in the form of a well founded multiset. However, the conventional rule for this representation is not one-to-one from a set of trees to the class of multisets representing such trees. With this in mind, we devise a method of uniquely representing trees by
establishing a one-to-one correspondence between trees and suitable permutations of well founded multisets, which we call tree structures. We give formal definitions of a tree structure and a subtree structure. Finally, we represent membrane structures in the form of tree structures. The work contained herein in this chapter has been published; see Singh and Peter (2011).
INTRODUCTION
A tree is an acyclic connected graph (having one source or trunk and several exits or leaves). It can also be defined as a partial order relation over a finite set with the smallest element. Note that if there is only one edge from a source node, then we have only one branch on the node. Formal definitions will be given later in this chapter. Trees have
served as handy tools in solving problems involving decisions and the flow of information from one point to another.
Every tree can be represented in the form of a wellfounded multiset – a multiset with an irreflexive and transitive ordering defined on it in order that no infinite descending sequence of elements occurs. We follow the Darshowitz-Manna ordering on multisets over a set of natural numbers which has been proved well founded (Darshowitz and
Manna, 1979). In the recent years, the representation of a finitely growing tree in the form of a well founded (cardinality–bounded) multiset seems to be a conventional choice. However, the said representation is not one-to-one from a set of trees to the class of multisets representing such trees. In order to achieve uniqueness, various permutations of the well founded multiset in consideration along with a suitable rule are adopted. We begin
with a binary tree, and generalize the approach to an n-nary tree and a general tree.
SOME APPLICATION AREAS
Trees are found in Mathematics, Management, Economics, Commerce, Biology, Computer Science, Statistics and Probability, just to mention but a few. In Managerial accounting (Hilton, 1996), a tree diagram in the form of an organizational chart was used to illustrate the organization of Aloha Hotels and Rresorts. In Computer Science (Bailey, 1999), the Huffman tree is used to compress bits so as to reduce the amount of storage that is necessary in a storage media. In Biology, Tailor (1996) shows the tree diagram representing the basic characteristics of meiosis showing one chromosome duplication followed by two nuclear and cell divisions. In Probability,
(Kemeny, 1957), we come across the tree measure for a sequence of repeated throws of a coin with either side labelled head or tail. In English language, we represent the classification of nouns in the form of a tree as in Eyisi (2006). As some membranes can contain several other membranes as indicated by Păun (2002), trees can also be used to study membranes in membrane computing.
CHAPTER SIX
CONCLUSION AND FUTURE DIRECTION
This work can be seen as a stepping stone to bringing DNA computing and the structure of membranes to a form in which mathematical tools and methods can be used to analyse the subject. In particular, the communications among membranes can be better interpreted.
As efforts are being made to simulate transition P system on digital computers (Rogozhin and Boian, 2003), it is interesting to observe that a membrane structure represented in the form of a Venn diagram or a tree diagram is not readily amenable to the computer at programming level, the use of multiset-based tree structures can be of great help.
We hope that this work will be helpful in providing tools to explore various applications of multiset-based model in areas of research especially in biology and computer science.
For further application, especially in computer science, table 5.1 proves useful in a data entry interface when writing a program to manipulate trees structures.
The application of the saw-like permutation can be exploited in describing various algebraic structures of a tree structure.
REFERENCES
- Alhazov, A., Margenstern, M., Rogozhin, V., Rogozhin, Yu. and Verlan S. (2005), Communicative P systems with minimal cooperation., in (Mauri, G. , Păun, Gh., PrezJimenez, M. J., Rozenberg, G., Salomaa, A., eds (2004). Membrane Computing. International Workshop WMC5, Milan, Italy. Revised Papers), LNCS 3365, SpringerVerlag, Berlin, 162-178.
- Amos, M. (1997), DNA Computation, A Thesis of the University of Warwick, Coventry CV4 7AL.
- Arroyo, F. Baranda, A., Castellanos, J. and Păun, Gh., (2002), Membrane Computing: The Power of (Rule) Creation, Journal of Universal Computer Science, vol. 8, no. 3, 369-381.
- Bailey, D. A. (1999), Java Structure McGraw-Hill.
- Blizard, W. (1989), Multiset theory. Notre Dame Journal of formal logic. Vol. 30, 1, 36-66.
- Blizard, W. (1991), The Development of Multiset Theory, Modern Logic, Vol 1, 319-352.
- Dershowitz, N. and Manna, Z. (1975), Proving Termination with Multiset Ordering, Comm. ACM, Vol. 22, 465-476.
- Dornhoff, L. L. and Hohn, F. E. (1978), Applied Modern Algebra, Macmillan Publishing Co.
- Eyisi, J. (2006.), A Grammar of English, the Student’s Companion. Rex Charles publications.
- Floyd R.W. (1967), Assigning meanings to Programs, Proc. Symp
