Multidisciplinary Creativity

Descriere

The book contains original papers dealing with Membrane Computing and Theoretical Computer Science. The topics include mathematical aspects of P systems, modelling of biological processes, combinatorics of words, grammar systems, tree languages, and randomness. Informal personal reflections conclude the book. The book is dedicated to Gheorghe Paun’s 65th birthday. Fragment: " Tissue P systems are biologically inspired computing devices based on co munication between cells of a tissue. From a complexity theoretic perspecti tissue P systems with cell division [11] or cell separation rules [10] are able solve NP-complete problems in polynomial time by trading space for time, i. creating in polynomial time exponentially many cells working in parallel. One of the assumptions underlying the normal definition of tissue P syste a feature that is critically exploited in the solution of NP-complete problem is that each cell can in principle directly communicate with every other cell (having a different label). While this is reasonable for small systems, it is certainly unreasonable when the number of cells grows exponentially with the input size (lor instance, the number of cells in a human body is about 3.72 x 1013 ^s 1.06 x 245 121, a number corresponding, e.g., to an instance of Boolean satisfiability with about 1r variables). Therefore, it is essential for large tissue P systems to take into account;' the placement of the cells in the three-dimensional Euclidean space. As an abstraction, we model the geometric space where the tissue P systen are located as a graph, where vertices are possible locations for cells and edg are interpreted as proximity, that is, as the possibility of the cells located in t two extremes to communicate. This spatial graph model is a direct generalisati of standard tissue P systems and include them as a particular case. In order to model systems that can actually be constructed, we characteri the spatial graphs that can be "embedded" in the three-dimensional. Euclidean space. This embedding has only two restrictions, that can be informally stated as follows: cells that are considered "near" in the spatial graph cannot be placed too far in 1R3, and cells that are considered "distant" cannot be placed too close in R3. Practically speaking, the spatial graph must represent not-too-distorted real world distances. The idea of giving a geometrical or topological dimension to models of P systems was previously investigated by Margenstern, with P systems in the hyperbolic space [7], by Barbuti et al., with spatial P systems [1], and by Csuhaj-Yuji' et al., with P systems associated with a topology limiting the interactions between objects [3]. As described in Section 3, these models are however rather different in scope and features from what is proposed in this paper. We show that these "realistic" tissue P systems are severely limited in their gbility to increase their number of cells when working in polynomial time (their growth falls from exponential to at most polynomial — actually cubic — in R3). This, as a consequence, limits their computational ability to P. Therefore, we can claim that the current algorithms solving NP-complete problems by means Of tissue P systems can only be used for small instances, where the assumption of direct communication among all the cells holds. For large instances the geometry of the Euclidean space cannot be ignored and, unfortunately, it does not seem to permit escaping from P. "