Membrane Computing: An Introduction

Front Cover
Springer Science & Business Media, Aug 1, 2002 - Computers - 420 pages
Like quantum computing or DNA computing, membrane computing is an unconventional model of computation associated with a new computing paradigm. The field of membrane computing was initiated in 1998 by the author of this book; it is a branch of natural computing inspired by the structure and functioning of the living cell and devises distributed parallel computing models in the form of membrane systems, also called P systems.
This book is the first monograph surveying the new field in a systematic and coherent way. It presents the central notions and results: the main classes of P systems, the main results about their computational power and efficiency, a complete bibliography, and a series of open problems and research topics. Thus, the book is indispensible reading for anybody interested in molecular computing.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Membrane Computing What It Is and What It Is Not
1
2 Prerequisites
7
211 The Structure of the Plasma Membrane
8
212 Transmembrane Transport
10
Mitosis
14
22 The Neuron
15
23 Elements of Computability
16
231 Basic Notions and Notations
17
524 Replicated Rewriting
199
525 Parallel Rewriting
208
53 Splicing Membrane Systems
211
54 Contextual Membrane Systems
223
55 InsertionDeletion Membrane Systems
226
56 Bibliographical Notes
231
6 Networks of Membranes
235
61 The Splicing Case
236

232 Operations with Strings and Languages
18
233 Chomsky Grammars
19
234 Characterizations Necessary Conditions
22
235 Lindenmayer Systems
24
236 Finite Automata Turing Machines
26
237 Regulated Rewriting
29
238 On the Difference Between CS and RE
39
239 Universal Turing Machines and Type0 Grammars
40
2310 Splicing InsertionDeletion Context Adjoining
42
2311 Elements of Complexity
45
2312 Multisets
49
24 Bibliographical Notes
50
3 Membrane Systems with SymbolObjects
51
32 Two Examples
55
33 The Power of the Simple Class
58
34 Basic Extensions
64
342 Priorities Among the Evolution Rules
70
343 Two Further Examples
71
344 The Power of Priority
74
345 The Power of Synchronization
77
35 A Formal Definition
85
36 Further Extensions
91
362 Controlling the Permeability of Membranes
93
363 Communication Controlled by Concentration
99
364 Creating Rules During the Computation
102
365 Using PromotersInhibitors
104
37 Systems with External Output
114
38 Bibliographical Notes
125
4 Trading Evolution for Communication
129
41 Systems with SymportAntiport
130
42 Computational Universality
133
43 Controls on the Use of Rules
141
44 Following the Traces of Objects
144
45 Systems with Carriers
153
46 Bibliographical Notes
159
5 Structuring the Objects
161
51 Rewriting Membrane Systems
162
52 Some Variants and Their Power
180
521 Rule Creation
181
523 Conditional Communication
186
62 Using SymportAntiport Rules
238
63 Neurallike Networks of Membranes
249
632 The Computational Power
256
633 The Computational Efficiency
267
64 Bibliographical Notes
269
7 Trading Space for Time
271
72 Using Membrane Division
273
721 Solving SAT in Linear Time
281
722 Solving the Hamiltonian Path Problem
286
723 Using Cooperative Rules
290
724 Is Membrane Division Necessary?
298
73 Using Membrane Creation
301
731 Solving SAT
311
732 Solving HPP
316
733 The Case of StringObjects
318
74 Using String Replication
321
75 Using Precomputed Resources
323
76 Bibliographical Notes
327
8 Further Technical Results
329
82 Unary Systems
340
83 A Representation of Contextfree Languages
344
84 Valuating the StringObjects
348
85 Systems with Enhanced Membrane Handling
351
86 Brief Excursion Through the Literature
354
862 Bidimensional Objects
357
864 Membrane Systems and Ambient Calculus
359
865 A Direct Construction of a Universal System
361
866 Further Research Topics
363
9 Attempts to Get Back to Reality
367
92 Getting Closer to the Cell by Gemmation
373
Bilayer Membranes
375
94 In Silico Implementations
379
95 Artificial Life Applications
384
96 A Simulation of Photosynthesis
392
Open Problems
399
Universality Results
401
References
403
Index
417
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information