From P systems to morphogenetic systems: an overview and open problems
- PDF / 1,821,224 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 3 Downloads / 153 Views
SURVEY PAPER
From P systems to morphogenetic systems: an overview and open problems Petr Sosík1 · Jan Drastík1 · Vladimír Smolka1 · Max Garzon2 Received: 23 July 2020 / Accepted: 6 October 2020 © Springer Nature Singapore Pte Ltd. 2020
Abstract Morphogenetic (M) systems are an abstract model of computation inspired by morphogenetic processes in living cells and organisms. They were created as a generalization of P systems with proteins on membranes. Abstract cells are not used as atomic elements but they can be assembled from simpler primitives called tiles with pre-defined shapes, sizes and changeable positions in 2D or 3D Euclidean space. This additional level of realism provides a closer relation to fields as synthetic or systems biology. We summarize known results on M systems which include studies of computational universality, computational efficiency in solving intractable problems, and we discuss their relation to other models of P systems. An important capability of M systems is their robustness under injuries and their self-healing properties which has been established theoretically and verified experimentally. Finally, we present results of computational experiments inspired by cell mitosis processes. All topics are accompanied with related open problems. Keywords Membrane computing · Self-assembly · Morphogenesis · Morphogenetic system
1 Introduction In the introductory part of the first monograph [1] on membrane computing, Gheorghe Păun characterizes this research field as a positive answer to the question: Can we...build a computing model based on the cell structure and functioning? To be more specific, membrane computing is characterized as the fourth branch of molecular computing, with a special focus on the role of membranes as the entities which topologically divide cells and multi-cellular organisms and, to a large extent, organize and control their life processes. Indeed, as a prominent example we can take the endoplasmic reticulum, a complex membrane system within a cell, with its crucial role in synthesis, modification, and transport of proteins. * Petr Sosík [email protected] Max Garzon [email protected] 1
Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Opava, Czech Republic
Computer Science, The University of Memphis, Memphis, TN, USA
2
Membrane computing research focuses primarily on the topological role of membranes separating abstract individual cells/compartments in multi-cellular systems. Different processes and concentration of objects/molecules in these compartments and their controlled transport through membranes are the crucial ingredients of most known models of membrane computing. The original model of P systems introduced in [2] uses multisets of objects placed in the regions of a hierarchic membrane structure which evolve by applying catalytic or non-cooperative rules in the maximally parallel way. Later a range of variants of P systems appeared, generalizing or extending the original concept. In particular, tiss
Data Loading...
