Contents

Chapter 1: DNA Computing and P-Systems

G. Păun From Cells to Computers: Computing with Membranes (P-Systems) 9

R. Siromoney Distributed Circular Systems 41

P. Bonizzoni, G. Mauri, C. Ferretti, and R. Zizza Separating some Splicing Models 55

C. Zandron, G. Mauri, and C. Ferretti Universality and Normal Forms on Membrane Systems 61

Chapter 2: CD Grammar Systems

E. Csuhaj-Varjú Grammar Systems: 12 Years, 12 Problems (Short version) 77

T. Bălănescu, M. Gheorghe, and M. Holcombe A Subclass of Stream X-machines with Underlying Distributed Grammars 93

H. Fernau, M. Holzer, and R. Freund Cooperating Distributed Grammar Systems with Exhausting Resources 113

K. Krithivasan and M. Sakthi Balan Distributed Processing in Deterministic PDA 127

V. Manca Logical Representations of Grammatical Systems 147

V. Mitrana Parsability Approaches in CD Grammar Systems 165

Chapter 3: Colonies and PC Grammar Systems

J. Gašo Unreliable Colonies - the Parallel Case 189

J. Kelemen A Note on Colonies 203

Gy. Vaszil Problems and Recent Results Concerning Parallel Communicating Lindenmayer Systems 215

H. Fernau PC Grammar Systems with Terminal Transmission 229

P. J. Abisha, K. G. Subramanian, and D. G. Thomas Pure Pattern Grammars 253

Chapter 4: Eco-Grammar Systems and Applications of Grammar Systems

B. Cases and M. Alfonseca Eco-Grammar Systems Applied to the Analysis of the Dynamics of Population in Artificial Worlds 265

M. D. Jiménez-López, and C. Martín-Vide Grammar Systems and Autolexical Syntax: Two Theories, One Single Idea 283

P. Sosík Conditional Tabled Eco-Grammar Systems and Random Context Grammars 297

M. Neubauer and M. Summerer A Graph Controlled Array Grammar System with Predefined Teams for the Recognition of Hand-written Characters 309

S. Ewert and T. Wessels Distributed Processing of Random Context Picture Grammars 329

Chapter 5: Other Models of Computing

M. Holcombe X-machines in Computing, Biology and Art 343

W. Kuich Full Abstract Families of Tree Series II 347

G. Niemann Regular Languages and Church-Rosser Congruential Languages 359

R. Freund, L. Staiger Communicating Machines on ω-Words 371