By Dr. Gheorghe Paun
ESI Special Topics,
February 2003
Citing URL - http://www.esi-topics.com/fbp/2003/february03-GheorghePaun.html
|
Dr. Gheorghe Paun
answers a
few questions about this month's fast breaking paper in the field of
Computer Science.
From
•>>February 2003
Field: Computer Science
Article Title:
"Computing with membranes"
Authors: Paun, G
Journal: J COMPUT SYST SCI
Volume: 61
Page: 108-143
Year: AUG 2000
* Romanian Acad, Math Inst, POB 1-764, Bucharest 70700, Romania.
* Romanian Acad, Math Inst, Bucharest 70700, Romania.
|
 Why
do you think your paper is highly cited?
It is both based on several "classic" theoretical
computer science tools/techniques (grammars, automata,
Lindenmayer systems, regulated rewriting, grammar systems), and
related to rather "modern" branches of computer
science (molecular computing in general, DNA computing in
particular); it is highly interdisciplinary (it proposes
computation models based on the structure and the functioning of
the living cell). The model is very versatile; many variants
were proposed, biologically or mathematically motivated. Most of
these variants have attractive computer science features:
universality and/or computational efficiency; they also promise
to have relevance from a biological point of view, as
algorithmic
models of the cell as a whole (or of other cell-like
systems).
Does
it describe a new discovery or a new methodology that's useful to
others?
It proposes a new branch of natural computing: a distributed,
parallel, and nondeterministic computing model, processing
multisets in a cell-like or tissue-like compartmental structure,
thus extending the field of molecular computing. Topics such as
communication, synchronization, (maximal) parallelism,
space-time trade-off, complexity, localization, etc. can find a
natural framework to be dealt with. This is also a (reductionistic)
global algorithmic model of the living cell, a kind of model the
biologists are waiting for in the near future.
What
were some of the circumstances that led you to do this research?
The research was done in the prolongation of several years of
work in DNA computing, which, in their turn, have continued many
years of work in formal language theory. Very specifically, the
paper was written in the framework of a project supported by The
Academy of Finland, during a stage in Turku Centre for Computer
Science, in the scientifically very "hot" group of
Arto Salomaa.
Could
you summarize the significance of your paper in layman's terms?
The goal is to abstract a computability model from the
structure and the functioning of the living cell. In short, in
the compartments determined by a "membrane structure"
(a cell-like hierarchical arrangement of membranes) one places
multisets of "objects" (corresponding to the chemicals
swimming in solutions) and "evolution rules"
(corresponding to chemical reactions). The rules are applied in
a maximal parallel (each object which can evolve by a rule from
the same compartment should evolve) nondeterministic (the
objects and the rules are randomly chosen) manner. The objects
can also pass through membranes (one can say that they are
"communicated" from one compartment to another one),
the membranes can be dissolved, divided, created. The
application of rules and the communication of objects can be
controlled in various ways, either biologically or computer
science motivated. A sequence of "transitions" from a
configuration of the system to another configuration is called a
"computation" and with a halting computation one
associates a result, e.g., in the form of the multiset of
objects present in a specified output membrane at the end of the
computation. Several variants were considered. Most of them are
computationally universal (they can compute all Turing
computable vectors of natural numbers); this holds true even in
certain cases where the computation is done by communication
only (no object evolves, but only changes the compartments where
it is placed). When an enhanced parallelism is available (e.g.,
via membrane division) polynomial solutions to NP-complete
problems can be obtained by a space-time trade-off. No
biological implementation was reported, but there are several
software implementations, as well as several (preliminary)
applications, mainly in simulating biological phenomena. Details
can be found at the web address http://psystems.disco.unimib.it,
as well as in the monograph Gh. Paun, Membrane Computing. An
Introduction, Springer-Verlag, Berlin, 2002.
Dr. Gheorghe Paun
Senior Researcher (Corresponding Member of the Romanian Academy)
Institute of Mathematics of the Romanian Academy
Bucharest, Romania
and
Member of the Research Group on Mathematical Linguistics
Rovira i Virgili University
Tarragona, Spain
|
ESI Special Topics,
February 2003
Citing URL - http://www.esi-topics.com/fbp/2003/february03-GheorghePaun.html
|
|
|
