Membrane Computing

1. Introduction: Membrane Computing — What It Is and What It Is Not.- 2. Prerequisites.- 2.1 The Biological Membrane.- 2.1.1 The Structure of the Plasma Membrane.- 2.1.2 Trans-membrane Transport.- 2.1.3 Cellular Division: Mitosis.- 2.2 The Neuron.- 2.3 Elements of Computability.- 2.3.1 Basic Notions and Notations.- 2.3.2 Operations with Strings and Languages.- 2.3.3 Chomsky Grammars.- 2.3.4 Characterizations, Necessary Conditions.- 2.3.5 Lindenmayer Systems.- 2.3.6 Finite Automata, Turing Machines.- 2.3.7 Regulated Rewriting.- 2.3.8 On the Difference Between CS and RE.- 2.3.9 Universal Turing Machines and Type-0 Grammars.- 2.3.10 Splicing, Insertion—Deletion, Context Adjoining.- 2.3.11 Elements of Complexity.- 2.3.12 Multisets.- 2.4 Bibliographical Notes.- 3. Membrane Systems with Symbol—Objects.- 3.1 A Simple Class.- 3.2 Two Examples.- 3.3 The Power of the Simple Class.- 3.4 Basic Extensions.- 3.4.1 Dissolving a Membrane.- 3.4.2 Priorities Among the Evolution Rules.- 3.4.3 Two Further Examples.- 3.4.4 The Power of Priority.- 3.4.5 The Power of Synchronization.- 3.5 A Formal Definition.- 3.6 Further Extensions.- 3.6.1 Weak Target Commands.- 3.6.2 Controlling the Permeability of Membranes.- 3.6.3 Communication Controlled by Concentration.- 3.6.4 Creating Rules During the Computation.- 3.6.5 Using Promoters/Inhibitors.- 3.7 Systems with External Output.- 3.8 Bibliographical Notes.- 4. Trading Evolution for Communication.- 4.1 Systems with Symport/Antiport.- 4.2 Computational Universality.- 4.3 Controls on the Use of Rules.- 4.4 Following the Traces of Objects.- 4.5 Systems with Carriers.- 4.6 Bibliographical Notes.- 5. Structuring the Objects.- 5.1 Rewriting Membrane Systems.- 5.2 Some Variants and Their Power.- 5.2.1 Rule Creation.- 5.2.2 Conditional Rewriting.- 5.2.3 Conditional Communication.- 5.2.4 Replicated Rewriting.- 5.2.5 Parallel Rewriting.- 5.3 Splicing Membrane Systems.- 5.4 Contextual Membrane Systems.- 5.5 Insertion—Deletion Membrane Systems.- 5.6 Bibliographical Notes.- 6. Networks of Membranes.- 6.1 The Splicing Case.- 6.2 Using Symport/Antiport Rules.- 6.3 Neural-like Networks of Membranes.- 6.3.1 Definitions and Examples.- 6.3.2 The Computational Power.- 6.3.3 The Computational Efficiency.- 6.4 Bibliographical Notes.- 7. Trading Space for Time.- 7.1 Complexity Classes for Membrane Systems.- 7.2 Using Membrane Division.- 7.2.1 Solving SAT in Linear Time.- 7.2.2 Solving the Hamiltonian Path Problem.- 7.2.3 Using Cooperative Rules.- 7.2.4 Is Membrane Division Necessary?.- 7.3 Using Membrane Creation.- 7.3.1 Solving SAT.- 7.3.2 Solving HPP.- 7.3.3 The Case of String—Objects.- 7.4 Using String Replication.- 7.5 Using Pre-computed Resources.- 7.6 Bibliographical Notes.- 8. Further Technical Results.- 8.1 Decidability Results.- 8.2 Unary Systems.- 8.3 A Representation of Context—free Languages.- 8.4 Valuating the String—Objects.- 8.5 Systems with Enhanced Membrane Handling.- 8.6 Brief Excursion Through the Literature.- 8.6.1 Generalized Sequential Membrane Systems.- 8.6.2 Bidimensional Objects.- 8.6.3 Membrane Systems and Stream X-machines.- 8.6.4 Membrane Systems and Ambient Calculus.- 8.6.5 A Direct Construction of a Universal System.- 8.6.6 Further Research Topics.- 9. (Attempts to Get) Back to Reality.- 9.1 Getting Closer to the Cell by Energy Accounting.- 9.2 Getting Closer to the Cell by Gemmation.- 9.3 Getting Closer to the Cell: Bilayer Membranes.- 9.4 In Silico Implementations.- 9.5 Artificial Life Applications.- 9.6 A Simulation of Photosynthesis.- Open Problems.- Universality Results.- References.