Average Reviews:
(More customer reviews)Beginning with neural networks almost half a century ago, bio-inspired computing has come a long way. This progress has been mostly in theoretical developments, but recently there has been an upsurge in practical applications, due mainly to the increase in computing power. This book gives an overview of a very interesting twist on bio-inspired computing, namely that of constructing a computational grammar based on the chemical and metabolic processes in a living cell. This approach is intriguing on the surface, but it remains to be seen whether it will result in useful algorithms for solving practical problems. A list of open research problems is given in the book for the reader interested in pushing forward the frontiers of the subject.
The author's approach is to justify membrane computing in the context of computational grammar, i.e. is it powerful enough to be modeled as a language in the Chomsky hierarchy or the hierarchy of Lindenmayer systems? He does show that it is, but he also wants to justify the view of membrane computing as being one in the paradigm of parallel computing, which strictly speaking is outside the realm of these hierarchies. The author reviews the relevant computability theory in chapter two of the book, with the content being fairly standard. The exception to this is the discussion of `regulated rewriting' and the notion of a `matrix grammar' with `appearance checking.'
Abstracting from the geometry of the living cell, a membrane structure consists of several membranes that are arranged in a hierarchical structure and are contained in a main membrane, called the skin. Membranes surround `regions,' and an `elementary' membrane is one that does not contain any other membranes. The regions contain `multisets' of `objects', these being abstractions of chemicals present in the compartments of a biological cell. The objects are represented by symbols from an alphabet chosen a priori, and they evolve according to given evolution rules. These rules are associated to the regions and are applied non-deterministically and in parallel, i.e. all objects that can evolve must do so. The objects can be moved between regions and the membranes can be dissolved, created, and divided. These processes thus result in the membrane system making a transition from one configuration to another, with all the transitions collectively constituting a `computation.' A `halting computation' results when the rules are exhausted, i.e. there is no rule that can be applied to an existing objects. The result of a halting computation is the number of objects in a specified output membrane.
A `symbol-object membrane system' or `P-system' is thus a construct consisting of an alphabet O of objects, a membrane structure consisting of a finite number M of membranes (M is called the `degree'), a collection of M strings representing multisets over O associating with the M regions, a collection of M evolution rules over O, and a designation of a membrane as being the output membrane. An evolution rule has the form U -> V, where U is a string over O and V is a string over the `target.' The length of U is called the `radius' and if the radius is greater than one the P-system is called a system `with cooperation' (otherwise `non-cooperative'). In analogy with chemical reactions, certain types of cooperative systems are called `catalytic' systems.
Early on in the book, the author shows that as defined, these P-systems are not powerful enough from the standpoint of generative grammars. This motivates extensions to the basic definition, such as the ability to dissolve membranes, the use of prioritization among the evolution rules, the removal of synchronization, controlling the permeability of membranes, controlling the concentration between regions, creating rules during the computation, and using promoters or inhibitors. For each of these extensions, the author proves (in extreme detail) various results on how they improve the computational power of ordinary P-systems in relation to the Chomsky and Lindenmayer hierarchies.
The author also narrows his discussion to membrane systems that are more faithful to their biological inspiration. One of these discussions involves computations that arise from merely changing the locations of the objects with respect to the membranes of a system, instead of changing the objects themselves. This entails bringing in objects from the environment, and the intake and outtake of objects through membranes. Systems that do this the author calls `symport/antiport' and he proves that such systems are `computationally universal' in the sense that they generate the family of length sets of recursively enumerable languages.
Not all of the book's content is devoted to theoretical developments, for the last chapter is devoted to discussions on how to use the computational models to actually build a model of the living cell. To do this one must take cognizance of the energy requirements of the cell, which has been neglected in the computational models in the rest of the book. His discussion here is interesting for he makes use of the concept of a `conformon', which, as the name implies, is essentially a local conformational strain of a biomolecule that is genetically determined and responsible for specific biological functions. The conformon concept has found some legitimacy from a physics standpoint recently (viewed as "packets" or "solitons" of conformational energy), but in this book the author is more concerned with using it as a device for computational grammar. In particular, he views a conformon as a pair consisting of a name and a number, the latter of which is the energy associated with the name information.
For this reviewer, the most interesting part of the book is the discussion on the simulation of photosynthesis. The membrane system consists of an external membrane representing the envelope membrane of the chloroplast, and the internal membrane representing the thylakoid membrane. It is a fascinating project to turn this analysis around and construct a real system consisting of vegetative matter that is powered by light and capable of running real algorithms with useful output.
Click Here to see more reviews about: Membrane Computing: 9th International Workshop, WMC 2008, Edinburgh, UK, July 28-31, 2008, Revised Selected and Invited Papers (Lecture Notes in ... Computer Science and General Issues)
This book constitutes the thoroughly refereed extended postproceedings of the 9th International Workshop on Membrane Computing, WMC 2008, held in Edinburgh, UK, in July 2008 under the auspices of the European Molecular Computing Consortium (EMCC) and the Molecular Computing Task Force of IEEE Computational Intelligence Society.The 22 revised full papers presented together with 5 invited papers went through two rounds of reviewing and improvement. The papers in this volume cover all the main directions of research in membrane computing, ranging from theoretical topics in mathematics and computer science to application issues. A special attention was paid to the interaction of membrane computing with biology and computer science, focusing both on the biological roots of membrane computing, on applications of membrane computing in biology and medicine, and on possible electronically based implementations.
No comments:
Post a Comment