Membrane Computing: 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers

Artiom Alhazov, Rudolf Freund, Yurii Rogozhin (auth.), Rudolf Freund, Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa (eds.)3540309489, 9783540309482

This book constitutes the thoroughly refereed extended postproceedings of the 6th International Workshop on Membrane Computing, WMC 2005, held in Vienna, Austria, in July 2005.

The 20 revised full papers presented together with 5 invited papers went through two rounds of reviewing and improvement. The papers in this volume cover all the main directions of research in membrane computing, ranging from theoretical topics in mathematics and computer science, to application issues, especially in biology. More specifically, these papers present research on topics such as: computational power and complexity classes, new types of P systems, relationships to Petri nets, quantum computing, and brane calculi, determinism vs. nondeterminism, hierarchies, the size of small families, algebraic approaches, and designing polynomial solutions to NP-complete problems through the use of membrane systems.

---

Table of contents :
Front Matter….Pages –
Computational Power of Symport/Antiport: History, Advances, and Open Problems….Pages 1-30
Structural Operational Semantics of P Systems….Pages 31-48
Some Recent Results Concerning Deterministic P Systems….Pages 49-54
Membrane Algorithms….Pages 55-66
On Evolutionary Lineages of Membrane Systems….Pages 67-78
Number of Protons/Bi-stable Catalysts and Membranes in P Systems. Time-Freeness….Pages 79-95
Symbol/Membrane Complexity of P Systems with Symport/Antiport Rules….Pages 96-113
On P Systems as a Modelling Tool for Biological Systems….Pages 114-133
Encoding-Decoding Transitional Systems for Classes of P Systems….Pages 134-143
On the Computational Power of the Mate/Bud/Drip Brane Calculus: Interleaving vs. Maximal Parallelism….Pages 144-158
A Membrane Computing System Mapped on an Asynchronous, Distributed Computational Environment….Pages 159-164
P Systems with Memory….Pages 165-180
Algebraic and Coalgebraic Aspects of Membrane Computing….Pages 181-198
P Systems and the Modeling of Biochemical Oscillations….Pages 199-208
P Systems, Petri Nets, and Program Machines….Pages 209-223
On the Power of Dissolution in P Systems with Active Membranes….Pages 224-240
A Linear Solution for QSAT with Membrane Creation….Pages 241-252
On Symport/Antiport P Systems and Semilinear Sets….Pages 253-271
Boolean Circuits and a DNA Algorithm in Membrane Computing….Pages 272-291
Towards a Petri Net Semantics for Membrane Systems….Pages 292-309
Quantum Sequential P Systems with Unit Rules and Energy Assigned to Membranes….Pages 310-325
Editing Distances Between Membrane Structures….Pages 326-341
Relational Membrane Systems….Pages 342-355
On the Rule Complexity of Universal Tissue P Systems….Pages 356-362
Non-cooperative P Systems with Priorities Characterize PsET0L….Pages 363-370
Back Matter….Pages –