Aspects of Molecular Computing: Essays Dedicated to Tom Head on the Occasion of His 70th Birthday (Lecture Notes in Computer Science, 2950)

Molecular computing is a rapidly growing subarea of natural computing. On the one hand, molecular computing is concerned with the use of bio-molecules for the purpose of actual computations while, on the other hand, it attempts to understand the computational nature of molecular processes going on in living cells. The book presents a unique and authorative state-of-the-art survey on current research in molecular computing: 30 papers by leading researchers in the area are drawn together on the occasion of the 70th birthday of Tom Head, a pioneer in molecular computing. Among the topics addressed are molecular tiling, DNA self-assembly, splicing systems, DNA-based cryptography, DNA word design, gene assembly, and membrane computing. Front Matter....Pages - Solving Graph Problems by P Systems with Restricted Elementary Active Membranes....Pages 1-22 Writing Information into DNA....Pages 23-35 Balance Machines: Computing = Balancing....Pages 36-48 Eilenberg P Systems with Symbol-Objects....Pages 49-60 Molecular Tiling and DNA Self-assembly....Pages 61-83 On Some Classes of Splicing Languages....Pages 84-105 The Power of Networks of Watson-Crick D0L Systems....Pages 106-118 Fixed Point Approach to Commutation of Languages....Pages 119-131 Remarks on Relativisations and DNA Encodings....Pages 132-138 Splicing Test Tube Systems and Their Relation to Splicing Membrane Systems....Pages 139-151 Digital Information Encoding on DNA....Pages 152-166 DNA-based Cryptography....Pages 167-188 Splicing to the Limit....Pages 189-201 Formal Properties of Gene Assembly: Equivalence Problem for Overlap Graphs....Pages 202-212 n -Insertion on Languages....Pages 213-218 Transducers with Programmable Input by DNA Self-assembly....Pages 219-240 Methods for Constructing Coded DNA Languages....Pages 241-253 On the Universality of P Systems with Minimal Symport/Antiport Rules....Pages 254-265 An Algorithm for Testing Structure Freeness of Biomolecular Sequences....Pages 266-277 On Languages of Cyclic Words....Pages 278-288 A DNA Algorithm for the Hamiltonian Path Problem Using Microfluidic Systems....Pages 289-296 Formal Languages Arising from Gene Repeated Duplication....Pages 297-308 A Proof of Regularity for Finite Splicing....Pages 309-317 The Duality of Patterning in Molecular Genetics....Pages 318-321 Membrane Computing: Some Non-standard Ideas....Pages 322-337 The P Versus NP Problem Through Cellular Computing with Membranes....Pages 338-352 Realizing Switching Functions Using Peptide-Antibody Interactions....Pages 353-360 Plasmids to Solve #3SAT....Pages 361-366 Communicating Distributed H Systems with Alternating Filters....Pages 367-384 Back Matter....Pages -

Molecular computing is a rapidly growing subarea of natural computing. On the one hand, molecular computing is concerned with the use of bio-molecules for the purpose of actual computations while, on the other hand, it attempts to understand the computational nature of molecular processes going on in living cells.

The book presents a unique and authorative state-of-the-art survey on current research in molecular computing: 30 papers by leading researchers in the area are drawn together on the occasion of the 70th birthday of Tom Head, a pioneer in molecular computing. Among the topics addressed are molecular tiling, DNA self-assembly, splicing systems, DNA-based cryptography, DNA word design, gene assembly, and membrane computing.

The P systems are a class of distributed parallel computing devices of a biochemical type, introduced in [2], which can be seen as a general computing architecture where various types of objects can be processed by various operations.