Paper Info
Title
A guide to membrane computing
Abstract
Membrane systems are models of computation which are inspired by some basic features of biological membranes. In a membrane system multisets of objects are placed in the compartments defined by the membrane structure, and the objects evolve by means of "reaction rules" also associated with the compartments, and applied in a maximally parallel, nondeterministic manner. The objects can pass through membranes, the membranes can change their permeability, they can dissolve, and they can divide. These features are used in defining transitions between configurations of the system, and sequences of transitions are used to define computations. In the case of symbol-objects, we compute a set of numbers, and in the case of string-objects we compute a set of strings, hence a language. Many different classes of such computing devices (now called P systems) have already been investigated. Most of them are computationally universal, i.e., equal in power to Turing machines. Systems with an enhanced parallelism are able to trade space for time and solve in this way (at least in principle), by making use of an exponential space, intractable problems in a feasible time.The present paper presents the basic ideas of computing with membranes and some fundamental properties (mostly concerning the computational power and efficiency) of P systems of various types.
Year
DOI
Venue
2002
10.1016/S0304-3975(02)00136-6
Theoretical Computer Science
Keywords
DocType
Volume
biological membrane,np-complete problems,p system,natural computing,computational power,membrane system,computing device,membrane computing,basic idea,chomsky hierarchy,basic feature,turing computability,membrane structure,membrane system multisets,exponential space
Journal
287
Issue
ISSN
Citations 
1
Theoretical Computer Science
175
PageRank 
References 
Authors
14.52
35
2
Search Limit
100175
Name
Order
Citations
PageRank
Gheorghe Paun12840369.48
Grzegorz Rozenberg252081039.94