|
Second Brainstorming Week on Membrane Computing
J.UCS Special Issue
Gheorghe Paun (Institute of Mathematics of the
Romanian Academy, Bucharest, Romania, and Department of Computer
Science and Artificial Intelligence Sevilla University, Spain)
gpaun@us.es
Mario J. PérezJiménez (Department of Computer Science and Artificial Intelligence
Sevilla University, Spain)
Mario.Perez@cs.us.es
Abstract: The present volume contains a selection of papers
elaborated during the "Second Brainstorming Week on Membrane
Computing", held in Sevilla, Spain, from February 2 to February
7, 2004, in the organization of the Research Group on Natural
Computing (RGNC) from the Department of Computer Science and
Artificial Intelligence of Sevilla University. The goal of this novel
type of meetings (the first edition was held in February 2003 in
Tarragona, Spain), is to gather together a number of active
researchers in membrane computing, for exchanging ideas, presenting
recent results, and working together for one week in an informal and
friendly environment.
The efficiency of such meetings, prepared in advance by a previous
interaction through internet, is very high, and this year the success
was still higher than the previous year. In total, 38 researchers were
present in Sevilla, com puter scientists, mathematicians, biologists,
of various ages and from various countries, and an impressive number
of research topics, problems, preliminary results were discussed and
then turned out into papers. The initial versions of these papers were
collected in a proceedings volume which was published soon after the
meeting as a technical report (no 1/2004) of RGNC, Sevilla University;
the volume, of about 460 pages, is available also through the web page
from http://psystems.disco.unimib.it.
Part of these papers, continued after the Brainstorming according to
the discussions held in Sevilla, further polished and additionally
refereed, are included in this volume; another series of papers were
selected for a special issue of Soft Computing.
Very shortly stated, membrane computing is a branch of natural
computing whose aim is to abstract a computing model from the
structure and the functioning of the living cell. Basically, a
membrane system (P system) is a distributedparallel computing model,
where multisets of symbol-objects are processed in the compartments
defined by a cell-like hierarchy of membranes.
These objects evolve by means of multiset rewriting-like rules
and/or by communication rules (such as symport/antiport rules) which
are applied in a maximally parallel (all objects which can evolve
should do it) non-deterministic (the objects to process and the rules
to apply are chosen in a random way) manner. There are many classes of
P systems, with biological or mathematical motivation. For instance,
the objects can be also strings of symbols, the membrane structure can
be described by a graph (the socalled tissue P systems), or can
itself evolve, e.g., by dissolution or by membrane division. Most of
these types of systems were proven to be computationally universal,
equivalent in power to Turing machines. In cases where an exponential
space can be created in a polynomial time - for instance, by means of
biologically well motivated operations, such as membrane division or
membrane creation - by trading space for time one can solve
computationally hard problems (typically, NP-complete problems) in
polynomial (often, linear) time. In the last years, membrane computing
also started to be used as a frame-work for modelling various
biological phenomena, mainly at the cell level, as well as a toolkit
for applications in linguistics, computer graphics, management,
etc.
A comprehensive presentation of the domain, at the level of the
spring of 2002, can be found in the monograph Gh. Paun, Membrane
Computing. An Introduction, Springer-Verlag, Berlin, 2002, while
the current bibliography of membrane computing (including many
downloadable papers) can be found at the above mentioned web page.
The papers which follow illustrate all main research directions
active in membrane computing: looking into biology for new ideas,
followed then mathematically; comparing various types of P systems
with Turing machines and their restrictions (in most cases, proving
universality results); looking for better results from various points
of view, such as the size of involved systems, their determinism, the
ingredients they use for reaching the power of Turing machines;
implementations on the usual computer (mainly for didactic purposes
and for applications in modelling biological phenomena); ways to
devise polynomial solutions to computationally hard problems, or
solutions to various problems, more efficient than in sequential
computing frameworks; tissuelike P systems, with the cells placed in
the nodes of a graph; ways to add noncrisp mathematical features to P
systems, such as probabilities, fuzzy sets or rough sets features.
What is missing is an illustration of another important trend in
membrane computing, namely applications of a biological nature. A
volume covering this topic (as well as other types of applications),
also containing papers elaborated during the Brainstorming, is in
preparation for Springer-Verlag.
As mentioned above, the meeting was organized by the Research Group on
Natural Computing from Sevilla University (http://www.gcn.us.es) - and all the
members of this group were involved in the work. Many participants
have used funds from the CE MolCoNet Project IST-2001-32008. The
Brainstorming also benefited from the support of the project
TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnología
of Spain, of the Acción Coordinada IMUS 2003, of the Research
Group PAI TIC 193 of the Junta de Andalucia, and of the Department of
Computer Science and Artificial Intelligence from Sevilla University.
Sevilla, Spain
April, 2004
Gheorghe Paun
Mario J. Pérez-Jiménez
|