Frontiers of Membrane Computing: Open Problems and Research Topics

Frontiers of Membrane Computing: Open Problems and Research Topics Marian Gheorghe1, Gheorghe P˘aun2,3, Mario J. P´erez-Jim´enez3– Editors 1Department of Computer Science, University of Sheffield Regent Court, Portobello Street, Sheffield S1 4DP, UK [email protected] 2Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania 3Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected] Summary. This is a list of open problems and research topics collected after the Twelfth Conference on Membrane Computing, CMC 2012 (Fontainebleau, France (23 - 26 August 2011), meant initially to be a working material for Tenth Brainstorming Week on Membrane Computing, Sevilla, Spain (January 30 - February 3, 2012). The result was circulated in several versions before the brainstorming and then modified according to the discussions held in Sevilla and according to the progresses made during the meeting. In the present form, the list gives an image about key research directions currently active in membrane computing. Introduction The idea of compiling a collection of open problems and research topics in membrane computing (MC) occurred during the Twelfth International Conference on Membrane Computing, CMC 12, held in Fontainebleau, Paris, France, from 23 to 26 of August, 2011 (see http://cmc12.lacl.fr/). The invitation to contribute to such a collection was formulated during CMC 12 (and after that reinforced by email) and several researchers answered this call. The result was circulated under the name of “mega-paper” (mega because it has much more co-authors than any other paper in MC...), meant to be a working material for the Tenth Brainstorming Week on Membrane Computing, Sevilla, Spain, January 30 - February 3, 2012 (BWMC 10). During CMC 12 there were also discussions and suggestions regarding some other topics which are not developed here; for this reason we briefly mention 172 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. (some of) them: exploring more systematically hypercomputation research ideas within MC area; focussing on translations between different classes of membrane systems (P systems) and studying complexity aspects related to these translations (the goal being to import results from a branch of MC to another one); identifying the most “natural” applications of P systems in modeling biological processes and producing a set of coherent and convincing case studies (a research volume on such applications in biology is now in progress); investigate in more details the dP automata, their efficiency and connections with communication complexity; look for biological applications of spiking neural P systems. Before presenting an overview of the paper we mention [7], [8] as key references for general MC topics. More specific MC topics, like MC and process calculi [1], interplay between MC and DNA computing [6] and conformon MC systems [3], are also well-established. Applications of MC in various areas can be found in [2]. The initial “mega-paper” was changed several times, incorporating discussions and progresses carried out during BWMC 10. The present version is considered a “closed” one (although such a project can never be closed); for further results related to the problems collected here the reader is invited to follow the MC website from [9]. In particular, one can find there the proceedings volumes, with all papers emerged in connection with the brainstorming. The texts received from the contributors were revised by their authors after BWMC 10, and appear below in the final form they have been submitted, with minimal editorial changes. In most cases, one gives the necessary (minimal) definitions, as well as the relevant bibliography. Of course, the reader is supposed to be familiar with basic elements of MC – for instance, from the sources mentioned at the end of this introduction. A quick introduction to MC is given at the beginning of this paper, just to help the reader not familiar with this research area to have a flavor of it. At the beginning of each section there are mentioned the main notions, from MC and from computability in general, supposed to be known in order to understand the problems which follow (sometimes, part of these notions are briefly introduced together with the problems). The authors of each “section” are mentioned, with affiliations and email addresses, so that the interested reader can contact them for further details, clarifications and cooperation in solving the problems. The order in which the problems are given below goes, approximately, from general issues to theory and then to applications. In what concerns the computability topics, there are sections devoted to both power and efficiency of P systems, considering them as numbers or strings generators or acceptors, in “old” versions (symport/antiport, catalytic, spiking neural P systems) or in recently introduced forms (polymorphic, dP systems), looking for generalizations (e.g., for “kernel P systems”) or for classic notions of language theory not yet extended to MC (such as control words); computational complexity is a vivid direction of investigation, addressing both time and space complexity (defining specific complexity classes, comparing them with existing classes, looking for possibilities of solving computationally hard problems (typically, NP-complete problems) in a polynomial time, Frontiers of Membrane Computing 173 by making use of the massive parallelism of P systems and trading-off space for time, with the space obtained by means of biologically inspired operations, such as membrane division and membrane creation). The term “fypercomputing” (following the model of “hypercomputing” = “passing beyond the Turing barrier”, with the initial “f” coming from “fast”) tries to call attention to a systematic study of “passing polynomially beyond the NP barrier”. All classes of P systems are considered: cell-like, tissue-like, (spiking) neural, and numerical. Moving to applications, one mentions issues related to the semantics, formal verification, possible bridges with reaction systems (a younger “sister” research area of natural computing, inspired from biochemistry). The applications refer both to the simulation of biological and bio-medical processes and to (somewhat unexpected) applications in approximate optimization (basically, distributed evolutionary algorithms, with the distribution controlled by means of membranes, and borrowing ingredients from MC), robotics (mobile robots controlled by means of numerical P systems), and computer graphics, as well as to more speculative ideas, dealing, for instance, with the functioning of the brain. The nature of questions range from local/technical open problems, asking to improve existing results, especially for a better delimitation of the borderline between universality and non-universality, between efficiency and non-efficiency (in particular, concerning the influence of some qualitative parameters, such as the number of membranes, the size of the rules, or qualitative features, such as the difference between deterministic and non-deterministic systems, using or not various types of rules), to “strategic” issues, for instance, relating MC with other research areas, such as computer science, biology, ecology, robotics and so on. Of course, many other precise problems or research ideas circulate within the MC community (or can be found in recent papers; see also the previous brainstorming volumes, where many problems are formulated, sometimes given in explicit lists; the “fate” of some of these open problems is recalled in the paper Gh. P˘aun, “Tracing Some Open Problems in Membrane Computing”, Romanian J. of Information Science and Technology, 10, 4 (2007), 303–314). Similarly, some of the problems proposed in the present paper or variants of them were already circulated within the MC community also before, a fact which should call attention to them (as an indication of both interest and difficulty). We are aware, on the one hand, that many other authors, who have not answered our request (in time), would have other problems to propose, and, on the other hand, that many people keep for them, for their immediate research, the “juicy” topics... Anyway, we hope that this collection will both raise the interest of the reader in approaching MC and, maybe, in participating in the future editions of the yearly BWMC. Because several sections below refer to the CMC 12 pre-proceedings and proceedings volumes, we also mention them below – [4] and [5], respectively. 174 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. References 1. G. Ciobanu: Membrane Computing. Biologically Inspired Process Calculi. The Publishing House of the “Al.I. Cuza” University, Ia¸si, 2010. 2. G. Ciobanu, Gh. P˘aun, M.J. P´erez-Jim´enez, eds.: Applications of Membrane Computing. Springer, Berlin, 2006. 3. P. Frisco: Computing with Cells. Advances in Membrane Computing. Oxford Univ. Press, 2009. 4. M. Gheorghe, Gh. P˘aun, S. Verlan, eds.: Twelfth International Conference on Membrane Computing, CMC12, Fontainebleau, France, 23–26 August 2011. LACL, Univ. Paris Est – Cr´eteil Val de Marne, 2011. 5. M. Gheorghe, Gh. P˘aun, G. Rozenberg, A. Salomaa, S. Verlan, eds.: Membrane Computing. 12th International Conference, CMC 2011, Fontainebleau, France, August 2011, Revised Selected Papers, LNCS 7184, Springer, Berin, 2012. 6. A. P˘aun: Computability of the DNA and Cells. Splicing and Membrane Computing. SBEB Publishing, Choudrant, Louisiana, USA, 2008. 7. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002 (Chinese translation in 2012). 8. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford Univ. Press, 2010. 9. The P Systems Website: www.ppage.psystems.eu. Contents 1. A Glimpse to Membrane Computing (The Editors) 2. Some General Issues (J. Beal) 3. The Power of Small Numbers (A. Alhazov) 4. Polymorphic P Systems (S. Ivanov, A. Alhazov, Y. Rogozhin) 5. P Colonies and dP Automata (E. Csuhaj-Varj´u) 6. Spiking Neural P Systems (L. Pan, T. Song) 7. Control Words Associated with P Systems (K. Krithivasan, Gh. P˘aun, A. Ramanujan) 8. Speeding Up P Automata (G. Vaszil) 9. Space Complexity and the Power of Elementary Membrane Division (A. Leporati, G. Mauri, A.E. Porreca, C. Zandron) 10. The P-Conjecture and Hierarchies (N. Murphy) 11. Seeking Sharper Frontiers of Efficiency in Tissue P Systems (M.J. P´erez- Jim´enez, A. Riscos-N´u˜nez, M. Rius-Font, ´ A. Romero-Jim´enez) 12. Time-Free Solutions to Hard Computational Problems (M. Cavaliere) 13. Fypercomputations (Gh. P˘aun) 14. Numerical P Systems (C. Vasile, A.B. Pavel, I. Dumitrache, Gh. P˘aun) 15. P Systems Formal Verification and Testing (F. Ipate, M. Gheorghe) 16. Causality, Semantics, Behavior (O. Agrigoroaiei, B. Aman, G. Ciobanu) Frontiers of Membrane Computing 175 17. Kernel P Systems (M. Gheorghe) 18. Bridging P and R (Gh. P˘aun) 19. P Systems and Evolutionary Computing Interactions (G. Zhang) 20. Metabolic P Systems (V. Manca) 21. Unraveling Oscillating Structures by Means of P Systems (T. Hinze) 22. Simulating Cells Using P Systems (A. P˘aun) 23. P Systems for Computational Systems and Synthetic Biology (M. Gheorghe, V. Manca, F.J. Romero-Campero) 24. Biologically Plausible Applications of Spiking Neural P Systems for an Explanation of Brain Cognitive Functions (A. Obtulowicz) 25. Computer Vision (D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo) 26. Open Problems on Simulation of Membrane Computing Models (M. Garc´ıa- Quismondo, L.F. Mac´ıas-Ramos. M.A. Mart´ınez-del-Amor, I. P´erez-Hurtado, L. Valencia-Cabrera) 1 A Glimpse to Membrane Computing Membrane computing (MC) is a branch of natural computing (introduced in [1], with the report version of the paper circulated as Turku Center for Computer Science – TUCS Report 208, in November 1998, see www.tucs.fi) which aims to abstract computing models from the structure and the functioning of the living cell and from populations of cells (e.g., tissues, organs), including the brain. One of the basic notions is that of a membrane, understood as a 3D vesicle, separating “an inside” and “an outside”, where objects can be placed and where specific biochemistries take place. The membranes can be arranged in a hierarchical structure (like in a cell, hence described by a tree) or in an arbitrary structure (like in tissues, hence described by a graph). The space between a membrane and the membranes placed immediately inside it (parent-children, in a tree) is called region or compartment. A membrane without any membrane inside is said to be elementary. In the case of a cell-like arrangement of membranes, the external membrane is called the skin. The space outside the skin membrane is called the environment (and similarly is called the space external to all membranes of a tissue-like membrane structure). A membrane structure can be formally represented by a rooted labeled tree (each membrane is identified by a label, which is then associated with the node of the tree associated with the membrane), or, correspondingly, by an expression of labeled parentheses, with a unique external pair of parentheses, corresponding to the skin membrane. The objects are present in the regions of a membrane structure and in the environment in the form of multisets, sets with their elements present in a given number of copies (sets with multiplicities of elements). The multiplicity can be finite (expressed by a natural number) or infinite/arbitrary (we say that an object with this 176 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. property is of ωmultiplicity). For the beginning, let us have in mind only atomic objects, represented by symbols of a given (finite) alphabet, and let us imagine that they correspond to the chemical compounds, from ions to macromolecules, which swim in water in the cell compartments. In this framework, it is convenient to represent the multisets by strings of symbols, with the number of occurrences of a symbol in a string corresponding to the multiplicity of that object in the multiset (that is, any permutation of a string represents the same multiset). These objects react, according to given evolution rules. The basic ones (often simply called “evolution rules”) are the multiset rewriting rules corresponding to the biochemical reactions taking place in a cell. They are of the form u→v, where uand vare multisets. Many other types of evolution rules are inspired by other biological operations. We mention here only the basic ones: symport/antiport correspond to the coupled passage of chemicals through (the protein channels embedded in) the cell membranes, membrane division corresponds to mitosis, membrane creation and membrane dissolution can also be associated with biological processes (the same with exo- and endocytosis, but we do not enter into details). There also are more complex types of rules, or rules inspired from computer science (broadcasting, communication between two membranes placed in a common environment), rules mimicking the way the neurons communicate by means of spikes (electrical impulses of identical shapes). Important is that both the rules and the objects are placed in compartments and that the rules act locally, on the objects in the same compartment. Objects can also pass through membranes, both in the cell-like case and in the tissue-like case, hence the compartments cooperate. There are several ways the rules are applied (several semantics). The most investigated one, corresponding to the parallelism of reactions in a solution, is the maximal parallelism: a maximal multiset of rules is used, where maximality is defined in the sense of multiset inclusion (no rules can be added to the multiset so that the obtained multiset of rules is still applicable to the multiset of objects present in the respective compartment). When several (maximal) multisets can be applied, the one to use is chosen nondeterministically. Many other possibilities were considered: sequential, limited parallelism, minimal parallelism (the idea is that each compartment which can use a rule – hence it is “alive” – has to use at least one rule, with natural extensions to P systems whose rules are not associated with compartments – as it is the case of symport/antiport systems, where the rules are associated with the membranes). In all these cases, the system is synchronized, a universal clock exists which measures the time in the same way for all membranes and with rules used, synchronously, in each time unit. The natural counterpart is that of asynchronous systems. Such a device, consisting of membranes, objects, evolution rules, is called a membrane system – currently called also a P system. Starting from an initial configuration (membranes and objects) of a P system and using the rules according to a chosen strategy, one obtains computations, sequences of transitions among configurations. If a configuration is obtained such that no rule can be applied, we say that the system halts. Several results can be Frontiers of Membrane Computing 177 associated with a halting computation, for instance, in the form of the number of objects present in the halting configuration in a designated elementary membrane. A P system can then be seen as a generative device, generating a set of numbers: because of nondeterminism, we have several computations, hence several numbers. Formally, a P system of the basic form (cell-like, with symbol objects, evolving by multiset rewriting rules) can be given as follows (for an alphabet A, we denote by A∗the set of all strings over A, including the empty string λ;A∗− {λ}is denoted by A+): Π= (O, µ, w1, . . . , wm, R1, . . . , Rm, i0),where mis the degree of the system, Ois the alphabet of objects, µis the membrane structure, with mmembranes, w1, . . . , wm∈O∗are multisets associated with the mregions of µ, R1, . . . , Rmare finite rules of the form u→vwhere uand vare multisets over Owith the objects in valso having target indications of the form in, out, here; an object with indication out exits the membrane, one with the indication here remains in the same region, and one with the target in enters any of the membranes delimiting the region from below, nondeterministically choosing the destination, i0is the label of the output membrane, the one where the result is obtained. A transition between two configurations C1, C2of Πis denoted by C1=⇒C2, and the set of numbers generated by Πis denoted by N(Π). The rules of the arbitrary form u→vare said to be cooperative, if u∈O, then the rule is called non-cooperative (it corresponds to context-free rules in a grammar); an intermediate case is that of catalytic rules, which are of the form ca →cv, where c∈Ois a catalyst, assisting the object a∈Oto get transformed into v∈O∗. When applying a rule u→v, the objects from uare consumed and those from vare produced. An antiport rule is of the form (u, out;v, in) with u, v ∈O∗; using such a rule (associated with a membrane i) means to move the multiset uoutside membrane i, simultaneously with bringing the multiset vinside the membrane. If one of the multisets u, v is empty, then the rule becomes a symport one. We do not give here further technical definitions or notations; the interested reader can consult any of the titles indicated in the end of the Introduction, especially the Handbook [8]. However, we mention informally a series of notions and of further classes of P systems. There are many possibilities to extend the previously introduced computing device and its functioning. Instead of counting objects in a compartment, we can consider as the result of a computation the sequence of objects sent to the environment (this is the so-called, external output), hence a P system can then 178 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. generate a language. A language is obtained also if we follow the trace of a special objects across membranes. Then, we can use a (symport/antiport) P system in the accepting mode: the objects entering the system from the environment are arranged in a string and we say that the string is accepted if the computation halts. In the case of tissue P systems, the objects can evolve inside membranes by multiset rewriting rules and can pass from a membrane to another one by antiport rules. The communication channels among membranes are hence implicitly defined by the provided rules for communication; a more complex case is that of population P systems, where there also are rules for establishing channels between cells and for destroying them. Besides rules for handling objects, we can also have rules for changing the membrane structure. We mentioned division, creation, and dissolution rules, exo- and endocytosis, but there also are separation, budding, gemmation rules. Observe the biological inspiration, although abstracted in a way which brings us far from biology – in their initial forms, P systems were not meant to be used as models with a biological relevance. The objects can be described by symbols, as above, but they can also have a structure, for instance, described by strings (processed by string operations, such as rewriting, DNA splicing, replication, insertion-deletion), or even more complex, such as 2D arrays, trees, etc. A special case is that of numerical P systems, where numerical variables are placed in the regions of a cell-like membrane structure, evolving by means of programs, composed of a production function (e.g., a polynomial), and a repartition protocol; in each compartment, the local variables are subject of a local production function, and the value of this function is distributed among the variables in that region and in the neighboring regions according to the repartition protocol (e.g., proportionally with given numbers, part of the program). The model, somewhat inspired from economics, can both generate sets of numbers, but also compute functions of several variables, a situation which is completely different from the generative-accepting functioning of usual object-based P systems. An interesting variant is that of P systems with objects bound on membranes (as actually is the case with many chemicals in a cell), and then with the rules evolving at the same time objects which are free inside regions and these fixed objects. Finally, let us mention the so-called spiking neural P systems (SN P systems), where membranes (representing neurons) are placed in the nodes of a graph, whose links represent synapses, holding several copies of a single object, corresponding to a spike; the spikes evolve by rules which first check the contents of the neuron (by means of a regular expression), consume a number of spikes and produce a number of spikes, which are sent, immediately or with a delay, to all neurons to which a synapse goes from the neuron where the rule was used. The spikes sent to the environment by a designated output neuron form the spike train produced by the system; numbers or strings can be associated with a spike train, hence again a generative device is obtained. Up to now, we mentioned only the generative mode (corresponding to grammars) of using a P system. A dual case (corresponding to automata) is the accepting mode: a number is introduced in a system, e.g., as the multiplicity of a Frontiers of Membrane Computing 179 specified object in a specified compartment, and the number is accepted if the computation halts. Strings can also be recognized, by bringing their symbols, one by one, in a system (e.g., in a symport/antiport one), with the string accepted if the computation halts. In all cases, we can also use a P system as a decidability machine: a decision problem (with YES/NO answer) is introduced in the system, encoded in a specified way in the form of a multiset, and the system says whether the problem (actually, its instance introduced in the initial configuration) has an affirmative answer by halting or by sending a special object yes into the environment. This is the usual way of investigating the computational complexity of P systems (the time or the space needed to solve a class of decidability problems). Most classes of P systems are computationally complete, equivalent with Turing machines (one also says that they are universal), even in restricted cases: small number of membranes, using only catalytic rules (with at least two catalysts: the power of one catalyst P systems is still open), symport/antiport rules of reduced sizes, SN P systems of restricted forms, etc. Similarly, many classes of P systems able to create an exponential working space in a linear time (the typical case is that of P systems using membrane division, also called with active membranes) can solve NP-complete problems (sometimes even PSPACE problems) in a polynomial time. The literature of MC abounds in results of these types. An important part of the research in MC deals with applications. Using P systems for modeling processes taking place in a cell or in complexes of cells, such as populations of bacteria, is expected; the model starts from biology, hence it is natural to return to biology. Several features make P systems attractive for the biologist (especially in comparison with the models based on differential equations): the direct connection with the biochemistry, which also means a high understandability, the multicompartmental structure, the easy scalability, the intrinsic discrete nature of the model, the easy programmability, the possibility to attach probabilities (reaction rates, stoichiometric coefficients) to the evolution rules, the emergent behavior of a P system (the overall evolution is not at all a “sum” of the parts evolution). All these applications are based on simulation programs (there are several such programs available – see the webpage of the domain, mentioned in the bibliography of the Introduction, [9]). Most of them run on the usual sequential computers, but there also are attempt to implement P systems on dedicated hardware, clusters and grids, on parallel hardware (such as NVIDIA graphical cards). A specialized programming language, P-lingua, was also elaborated. Also somewhat expected are the applications in modeling and simulating ecosystems (we have “membranes” where several agents interact, like the chemicals in a cell). Not so expected however are the applications in approximate optimization (distributed evolutionary computing), computer graphics (following the style of L systems based graphics, but also recent attempts to process images in the parallel framework of P systems), while the recent applications of numerical P systems in controlling mobile robots is completely unexpected. 186 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. iR for all 1 ≤i≤m. The string wh,h∈H, is the initial content of the membrane with label h. The label iout indicates the region where the output of the system will be read from. We will describe the mapping φlater on. Observe that the description of the system does not include any rule. Instead, the contents of the membranes with labels iL and iR are interpreted as the lefthand side and right-hand side of the rule irespectively. At every step, the rules are applied in the usual way. As a result of application of the rule i, the right-hand side of the rule (the content of iR) is injected into φ(i). The latter mapping is defined as follows: φ:{1, . . . , m} → Tar,Tar ={inj|j∈His an inner membrane of p} ∪ {out, here}, where p∈His the label of the membrane containing the rule i(the membranes iL and iR). For further information we refer the reader to [1]. Polymorphic P systems have not yet been explored sufficiently well. In the following paragraphs we list some open problems which we find of interest. •Solve hard problems. It has been shown that polymorphic P systems can solve certain problems faster than any other P system model (for example, they generate n2in O(1) and generate 22nin O(n)). So far, only relatively simple problems were considered, but we believe that the polymorphic model has the potential to facilitate solving much harder problems. For example, possibilities to find the Gr¨obner basis using polymorphic P systems are currently being considered. •Characterize problems which may be solved faster. A more general question, on the other hand, is to define the class of problems which can be solved more efficiently using polymorphic P systems. It has been observed that, for multiplication, linear speed-up was introduced; a much more systematic research in this direction is necessary. In particular, it is unclear whether it is possible to use the polymorphism to construct exponential workspace for solving intractable problems in polynomial time. •Polymorphic P systems with active membranes. Polymorphic P systems are a fairly simple model at the moment. This means, in particular, that certain extensions are possible. We would like to particularly stress the perspectives of considering polymorphic P systems with active membranes, where the membrane structure itself does not stay constant. Such a combination is a very powerful one, therefore it is important to establish some restrictions which will define an as simple as possible, yet sufficiently powerful, construct. •The power of the most restricted variant. Another way to explore polymorphic P systems is characterizing the power of models with the minimal number of additional ingredients (non-cooperative rules, no rules with empty left-hand side, no target indications). In [1] it is shown that even this model can easily achieve superexponential growth; it is important to know how powerful polymorphism on its own is. •Self-assembly. Finally, we make the observation that rules in polymorphic P systems may be treated as results of interaction of couples of initially indepen- Frontiers of Membrane Computing 187 dent membranes, which have gained additional capabilities by connecting to each other. The whole polymorphic P system may be treated as a stage in the process of interaction of membranes in a system of membranes. This brings about, in particular, the question of self-assembly of membrane structures. References 1. A. Alhazov, S. Ivanov, Yu. Rogozhin: Polymorphic P systems. 11th International Conference on Membrane Computing (M. Gheorghe et al., eds.), CMC 2010, Jena, Germany, LNCS 6501, Springer, Berlin, 2010, 81–94. 5 P Colonies and dP Automata Erzs´ebet Csuhaj-Varj´u Department of Algorithms and Their Applications Faculty of Informatics, E¨otv¨os Lor´and University, Budapest, Hungary [email protected] Required Notions: tissue-like P system, P colony, dP automaton 5.1 P Colonies P colonies are variants of very simple tissue-like P systems, modeling a community of very simple cells living together in a shared environment (for basic information see [8]). In the basic model, the cells (or agents) are represented by a collection of objects and rules for processing these objects. The agents are restricted in their capabilities, i.e., only a limited number of objects, say, kobjects, are allowed to be inside any cell during the functioning of the system. Number kis said to be the capacity of the P colony. The rules of the cells are either of the form a→b, specifying that an internal object ais transformed into an internal object b, or of the form c↔d, specifying the fact that an internal object cis sent out of the cell, to the environment, in exchange of the object d, which is present in the environment. After applying these rules in parallel, a cell containing the objects a, c will contain the objects b, d. With each cell, a set of programs composed of such rules is associated. In the case of P colonies of capacity k, each program has krules; the rules of the program must be applied in parallel to the objects in the cell. The cells of a P colony execute a computation by synchronously applying their programs to objects inside the cells and outside in the environment. At the beginning of the computation, performed by a given P colony of capacity k, the 188 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. environment contains arbitrarily many copies of a distinguished symbol e, called the environmental symbol (and no other symbols); furthermore, each cell contains kcopies of e. When a halting configuration is reached, that is, when no more rules can be applied, the result of the computation is read as the number of certain types of objects present in the environment. P colonies have been extensively examined during the years. It was shown that these simple constructs are computationally complete computing devices even with very restricted size parameters and with other syntactical or functioning restrictions. Several extensions of the model have already been investigated as well: P colonies with dynamically varying environment (eco-P colonies) [1] or PCol automata [2], constructs where the behavior of the cells is influenced by direct impulses coming from the environment step-by-step. In the case of a PCol automaton a tape with an input string is given with the P colony, i.e., the model is augmented with a string put on an input tape to be processed by the P colony. Except PCol automata, P colonies have been considered as generating devices, but the construct can also be considered as a (multiset) accepting device (called accepting P colony or P colony acceptor), possibly working in an automaton-like fashion as well. In the following we propose problems and problem areas in this direction. To define such a model, suppose that we have a P colony Πof capacity kand initialize the environment with a given finite multiset of symbols Mwhere each symbol is different from the environmental symbol e. Let also consider an initial configuration, i.e., let us dedicate an initial state to any cell and let us distinguish a set of accepting configurations. Then, we say that Mis accepted by Π, if after performing a finite computation (in some computation mode) the environment consists of only symbols e. It is easy to see that we may consider several variants of this model. For example, •we can limit the number of symbols in the environment (not necessarily with a finite constant, but with some function of the size of the P colony) and study the computational power of these systems with limited workspace for the computation, •we can consider the multisets in the environment during the computation as permutations of words (or map them to words in some other way) being on the input tape of an automata and study the relation of these constructs and classical automata; •we can map the sequences of multisets of objects entering each cell during the computation to words being on the input tape of a multitape or multihead automata and describe the correspondence between these constructs and the classical multitape or multihead automata variants. By introducing double alphabets as in the case of dP automata for describing two-way multihead finite automata ([3]), automata with two-way motion of heads can also be interpreted in the framework of accepting P colonies. Frontiers of Membrane Computing 189 The concept of accepting P colonies can be extended in some other manners as well. For example, we do not fix the number of cells in the P colony in advance but it is determined by the number of non-environmental symbols in the environment at the beginning. Spatial P colonies can also be defined. In this case spatial parameters are added to the cells and a neighborhood relation among the components is given; a cell can import only such symbols from the environment which were issued by its neighbors (are placed in its own environment). Accepting P colonies can be related to cellular automata as well. One natural idea is to define P colonies corresponding to one-way cellular automata, which are linear arrays of identical copies of deterministic finite automata, called cells, working synchronously at discrete time steps. Each cell is connected to its immediate neighbors to the right. The cells are identified by positive integers. The state transition depends on the current state of a cell itself and the current state of its neighbor. An input word is accepted by a one-way cellular automaton if at some step in the course of the computation the leftmost cell enters an accepting state. A particular variant of one-way cellular automata is the one where only a fixed number, say k, cells are given. This works similarly to the unrestricted case, but the input is processed in a different manner, namely, the input is not given at the beginning, but it is processed by the rightmost cell, symbol by symbol. Since the neighborhood can be defined in P colonies with emitting special symbols (signals) in the environment and any cell in the P colony may have only a finite number of configurations (states), the reader may observe that the two computational models, the accepting P colony and the k-cell one-way cellular automaton are strongly related. Obviously, more general cellular automata models can also be described by P colony acceptors. For example, the above extension of the concept of P colonies where the number of cells is determined by the number of initial non-environmental symbols can correspond to the unrestricted case. We can also model d-dimensional cellular automata (d≥1) by defining the neighborhood relation between cells of P colonies in an appropriate manner. Cellular automata theory has been a highly elaborated field of nature-motivated, parallel computing (see, for example, [5], [6], [7]), thus by building bridges between P colony theory and cellular automata theory, many interesting problems can also be studied. 5.2 dP Automata In addition to comparing accepting P colonies to variants of classical automata, we may explore the differences and similarities between these constructs and (finite) dP automata as well. A detailed study in this direction would also help in better understanding the nature of these two constructs. P automata are variants of antiport P systems accepting strings in an automaton-like fashion (for a summary on P automata, see Chapter 6 of [8]). The notion of a distributed P automaton (dP automaton in short) was introduced in [9]. Such a system consists of a finite number of component P automata which have 190 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. their separate inputs and which also may communicate with each other by means of special antiport-like rules. A string accepted by a dP automaton is obtained in [9] as the concatenation of the strings accepted by the individual components during a computation performed by the system. A dP automaton is called finite if it has only a finite number of different configurations. The computational power of dP automata was studied in [9], [4], [10], and [11]. In [3] a connection between finite dP automata and non-deterministic multihead finite automata was explored. It was shown that the language of a nondeterministic one-way multi-head finite automaton and the language of a nondeterministic two-way multi-head finite automaton can be obtained as so-called weak agreement language or strong agreement language of a one-way, i.e., a usual finite dP automaton, and a two-way finite dP automaton. The reader may easily observe that finite dP automata, P colony acceptors and cellular automata are closely related concepts. Their comparative study would be a promising and very useful area in P systems theory. Acknowledgement. Work supported in part by the Hungarian Research Fund “OTKA”, project K75952. References 1. L. Cienciala, L. Ciencialov´a: Eco-P colonies. Proc. WMC 2009, LNCS 5957 (Gh. P˘aun et al., eds.), Springer, 201–209. 2. L. Ciencala, L. Ciencialov´a, E. Csuhaj-Varj´u, Gy. Vaszil: PCol automata: Recognizing strings with P colonies. Proc. BWMC 2010, Sevilla, 2010 (M.A. Mart´ınez-del-Amor et al., eds.), F´enix Editora, Sevilla, 2010, 65–76. 3. E. Csuhaj-Varj´u, Gy. Vaszil: A connection between finite dP automata and multihead finite automata. Proc. Twelfth International Conference on Membrane Computing, Fontainebleau, 23-26 August, 2011 (M. Gheorghe et al., eds.), 109–126. 4. R. Freund, M. Kogler, Gh. P˘aun, M.J. P´erez-Jim´enez: On the power of P and dP automata. Annals of Bucharest Univ. Math.-Informatics Series, 63, 2009, 5–22. 5. M. Kutrib: Nature-based problems in cellular automata, Proc. CiE 2011, LNCS 6735, Springer, 2011, 171–180. 6. M. Kutrib, J. Lefevre, A. Malcher: The size of one-way cellular automata. Proc. Automata 2010: Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 71–90. 7. M. Holzer, M. Kutrib: Cellular automata and the quest for nontrivial artificial self-reproduction. Proc. Conf. on Membrane Computing, CMC 2010, LNCS 6501, Springer, 2010, 19–36. 8. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing, Oxford Univ. Press, 2010. 9. Gh. P˘aun, M.J. P´erez-Jim´enez: Solving problems in a distributed way in membrane computing: dP systems, International Journal of Computers, Communication & Control, V(2), 2010, 238–250. 10. Gh. P˘aun, M.J. P´erez-Jim´enez: P and dP automata: A survey. Rainbow of Computer Science (C.S. Calude et al., eds.), LNCS 6570, Springer, 2011, 102–115. Frontiers of Membrane Computing 191 11. Gh. P˘aun, M.J. P´erez-Jim´enez: An infinite hierarchy of languages defined by dP systems. Theoretical Computer Sci., 431 (2012), 4–12. 6 Spiking Neural P Systems Linqiang Pan, Tao Song Key Laboratory of Image Processing and Intelligent Control Department of Control Science and Engineering Huazhong University of Science and Technology, Wuhan, Hubei, China [email protected], [email protected] Applications of spiking neural P systems are proposed and some problems related to such applications are formulated. Required Notions: spiking neuron, SN P system, spiking neural network Spiking neural P systems (SN P systems, for short) were introduced in [4] as a class of distributed and parallel computing models inspired by spiking neurons. In an SN P system, the neurons are placed in the nodes of a directed graph. The content of each neuron consists of a number of copies of a single object type, called the spike. Each neuron contains a number of firing and forgetting rules. Firing rules allow a neuron to send information to other neurons in the form of electrical impulses (also called spikes) which are accumulated at the target cells. The applicability of each rule is determined by checking the content of the neuron against a regular set associated with the rule. A forgetting rule removes a specified number of spikes from the neuron. In each time unit, if a neuron can use some of its rules, firing or forgetting, then one of the rules must be used. The rule to be applied is nondeterministically chosen. One of the neurons is designated as the output neuron of the system, and its spikes are also sent to the environment; their sequence is called the spike train generated by the system. Several results of a computation can be defined associated with the spike train (strings or numbers). SN P systems use individual spikes allowing to incorporate spatial and temporal information in computation, which corresponds to the fact that neurons use spatial and temporal information of incoming spikes to encode their message to other neurons, where the number and timing of spikes matters. In the above sense, SN P systems fall into the third generation of neural network models [6]. Many computational properties of SN P systems have been studied (but many of them raise further research topics, but we do not refer to them here). SN P systems were proved to be computationally complete as number computing devices [4], language generators [1, 2], and function computing devices [8]. SN P systems were also used to (theoretically) solve computationally hard problems in a feasible 192 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. time [5, 7]. In contrast with the relatively rich theoretical results, the practical applications of SN P systems are few (although some attempts are already made, e.g., Hebbian learning in the framework of SN P systems [3]). However, as a representative of the third generation of neural network models, spiking neural networks (SNNs) could have very hands-on applications such as speech recognition, learning, associative memory, function approximation (see, e.g., Information Processing Letters, 95, 2005), and have proved to be useful in neuroscience. It is interesting to move the SN P systems investigations towards applications. In the following, we list some problems which we find of interest. •In SN P systems, the use of spike timing information is based on regular expressions, which can be considered as an integrate-and-fire scheme. The scheme of regular expressions is quite different from the traditional ones, such as the sigmoidal scheme. What is the advantage of the scheme of regular expressions from the application point of view? Can the two schemes (the regular expression and the sigmoidal one) be related? •What ingredients can be added to SN P systems for practical applications (maybe, noise, randomness)? •What are the specific real world problems where SN P systems have a practical advantage over other SNNs? •How can some variants of SN P systems be designed such that they would deal with features of more biological plausibleness? References 1. H. Chen, M. Ionescu, T.-O. Ishdorj, A. P˘aun, Gh. P˘aun, M.J. P´erez-Jim´enez: Spiking neural P systems with extended rules: universality and languages. Natural Computing, 7 (2008), 147–166. 2. H. Chen, R. Freund, M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez: On string languages generated by spiking neural P systems. Fundamenta Informaticae, 75 (2007), 141–162. 3. M.A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez: Hebbian learning from spiking neural P systems view. Proc. WMC9 2008 (D. Corne et al., eds.), LNCS 5391, Springer, Berlin, 2009, 217–230. 4. M. Ionescu, G. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71 (2006), 279–308. 5. T.-O. Ishdorj, A. Leporati, L. Pan, X. Zeng, X. Zhang: Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theoretical Computer Science, 411 (2010), 2345–2358. 6. W. Maass: The Third Generation of Neural Network Models. Technische Universitat Gr¨az, 1997 7. L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez: Spiking neural P systems with neuron division and budding. Science China Information Sciences, 54 (2011), 1596–1607. 8. A. P˘aun, Gh. P˘aun: Small universal spiking neural P systems. BioSystems, 90 (2007), 48–60. Frontiers of Membrane Computing 193 7 Control Words Associated with P Systems Kamala Krithivasan1, Gheorghe P˘aun2, Ajeesh Ramanujan1 1Department of Computer Science and Engineering Indian Institute of Technology Madras, Chennai, India [email protected] 2Institute of Mathematics of the Romanian Academy Bucharest, Romania, and Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] Ways to associate a control word with a computation in a P system are proposed and some of the problems which are natural to be investigated in this respect are mentioned. Required Notions: Szilard language, Chomsky hierarchy, cell P system, SN P system, parallelism Control words are almost never considered in membrane computing – actually, we know no paper dealing with this issue, although generating or recognizing languages are central research topics (with the languages identified by the sequence of symbols entering or leaving a P system, or by traces of certain symbols in their passage across membranes). The reason is the fact that in the same step of a computation several rules are used, possibly with several labels, hence the control word is not clearly defined. On the other hand, a sort of bidimensional control word was introduced already during the first BWMC, in [1], under the name of Sevilla carpet, as a way to describe the rules used in a computation and their multiplicity in each step, but not as a way to define a control language associated with the computations in a P system. A possible solution to the above difficulty is to consider a sequence of multisets of labels, those labels associated with all rules applied in a given step. Then, a string of symbols can be obtained following the ideas also used for accepting P systems: take a function from multisets to strings and build the string(s) obtained by concatenating the strings associated with the multisets. For instance, all permutations of the labels in a multiset can be considered, as in [3], or only one specific string (maybe a symbol) associated with the multiset, like in [2]. Another idea was recently introduced in [4], starting from the following restriction: all rules used in a computation step should have the same label, or they can also be labeled with λ. The definition in [4] is given for SN P systems, but it works for any type of P systems, not only for SN P systems. 194 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. Indeed, let us consider a P system Π, of any type, with the total set of rules (the union of all sets of rules associated with compartments, membranes, neurons – as it is the case) denoted with R. Consider a labeling mapping l:R→B∪{λ}, where Bis an alphabet. We consider only transitions s=⇒bs′, between configurations s, s′of Π, which use only rules with the same label band rules labeled with λ. We say that such a transition is label restricted. With a label restricted transition we associate the symbol bif at least one rule with label bis used; if all used rules have the label λ, then we associate λto this transition. Thus, with any computation in Πstarting from the initial configuration and proceeding through label restricted transitions we associate a (control) word. Consider also a criterion Cof the correct termination of a computation (e.g., halting or reaching a configuration from a given set Fof final configurations, or both of these, etc.) The language of control words associated with all label restricted computations in Πwhich are correctly terminated (with respect to C) is denoted by SzC(Π) (with Sz coming from Szilard, as usual in language theory). Now, a series of natural problems can be formulated: investigate the languages of control words for (i) various classes of P systems, with (ii) various criteria C, in particular, (iii) allow only transitions which use at least a rule labeled by b∈B. When λtransitions are accepted, characterizations of RE languages are expected, but when each step produces a symbol, there is no possibility for “hidden work”, the computation has the same length as the control string, so that the generated language is recursive. In this latter case the comparison with language families in Chomsky hierarchy is of interest (with the conjecture that languages of the forms {xx |x∈V∗},{xxR|x∈V∗}, where card(V)≥2 and xris the mirror image of x, cannot be obtained as the language of control words of a P system. In particular, the languages SzC(Π) can be associated with SN P systems, with or without anti-spikes. We expect interesting (language theory) results in this research area. References 1. G. Ciobanu, Gh. P˘aun, Gh. S¸tef˘anescu: Sevilla carpets associated with P systems. Proc. Brainstorming Week on Membrane Computing (M. Cavaliere et al., eds.), Tarragona Univ., TR 26/03, 2003, 135–140. 2. E. Csuhaj-Varj´u, Gy. Vaszil: P automata or purely communicating accepting P systems. Membrane Computing, International Workshop, WMC-CdeA, Curtea de Arge¸s, Romania, August 19-23, 2002, Revised Papers (Gh. P˘aun et al., eds.), LNCS 2597, Springer, 2003, 219–233. 3. M. Oswald: P Automata, PhD Thesis, TU Viena, 2003. 4. A. Ramanujan, K. Krithivasan: Control words of spiking neural P systems. Paper in preparation. Frontiers of Membrane Computing 195 8 Speeding Up P Automata Gy¨orgy Vaszil Department of Computer Science, Faculty of Informatics University of Debrecen, Hungary [email protected] The issue of efficient parallelization of languages with respect to dP automata is discussed (especially, the dependence on the multiset-to-strings functions which are used to define the input language). Required Notions: Regular language, context-sensitive language, P automata and dP automata (accepted multiset sequence, input mapping, accepted language) This section deals with the possibility of speeding up P automata computations (in a similar sense as a linear speedup for Turing machines is possible), a problem which is important from the point of view of the efficiency of the parallelization of P automata computations with distributed P automata. AP automaton, introduced in [2], is an antiport P system placed in an environment, from where a sequence of input multisets is read during the computation. A multiset sequence is accepted, if the computation ends in an accepting configuration, and the accepted multiset sequence is interpreted as a string (a sequence of symbols) using a so called input mapping f:V∗→2T∗where Tis a finite alphabet and Vis the object alphabet of the P automaton. (We assume that fis nonerasing, that is, f(u) is the empty word for some multiset u∈V∗, if and only if uis empty.) The language accepted by a P automaton Πwith respect to fis defined as L(Π, f) = {f(v1). . . f(vs)|v1,. . . , vsis an accepted multiset sequence of Π}. It is obvious that the choice of the mapping fhas a great influence on the accepting power of the P automaton, so let us take a closer look at the mappings we can use. Let f:V∗→2T∗, and (1) let us denote fwith fperm, if and only if V=T, and for all v∈V∗, we have f(v) = {u|uis a permutation of v}. Moreover, (2) we say that f∈TRANS, if and only if for any v∈V∗, we have f(v) = {w} for some w∈T∗which is obtained by applying a finite transducer to the string representation of the multiset v(as wis unique, the transducer must be constructed in such a way that all string representations of the multiset vas input result in the same w∈T∗as output, and moreover, as fshould be nonerasing, the transducer produces a result with w=λfor any nonempty input). Let us recall from [6] that there are simple linear languages which cannot be accepted by P automata with fperm, for example L={(ab)n(ac)n|n≥1}is such a language. On the other hand, the class of languages accepted with fperm also contains non-context-free context-sensitive languages ({anbncn|n≥1}for example), which means that it is incomparable with the class of linear and of context-free languages. (Although it contains all regular languages, see [3].) In 202 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. 11 Seeking Sharper Frontiers of Efficiency in Tissue P Systems Mario J. P´erez-Jim´enez1, Agust´ın Riscos-N´u˜nez1, Miquel Rius-Font2,´ Alvaro Romero-Jim´enez1 1Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] 2Department of Applied Mathematics IV Universitat Polit´ecnica de Catalunya, Casteldefels, Spain [email protected] In a P system, there are several ingredients which concur to their efficiency; varying them, one can get efficient systems (able to solve computationally hard problems in polynomial time) or non-efficient systems (e.g., solving NP-hard problems in an exponential time). The borderline between efficiency and non-efficiency is thus a problem of a central interest. This issue is explored here for tissue P systems, where the respective research started later than for cell P systems. Required Notions: tissue P systems, complexity classes, cell division, cell separation, symport/antiport rule Atissue P system with symport/antiport rules Π= (Γ, E,M1, . . . , Mq,R, iout), of degree q≥1 can be viewed as a set of qcells, labeled by 1, . . . , q, with an environment labeled by 0 which initially have an arbitrary number of copies of some kind of objects, and a set of rules which can be of several types: communication, division or separation (see [3, 4] for details). For each natural number k≥1, TDC(k) (respectively, TDS(k) or TDA(k)) is the class of recognizer tissue P systems with cell division and communication rules (allowing only symport or antiport rules, respectively) of length at most k. Similarly, by considering separation rules instead of division rules, we denote TSC(k), TSS(k) and TSA(k) respectively. We denote by PMCRthe set of all decision problems which can be solved in a uniform way and polynomial time by means of families of systems from a class Rof recognizer tissue P systems. (A) Tissue P systems with cell division and with cell separation By using the dependency graph technique, it has been proved that P= PMCT DC(1) =PMCT SC(1) [2, 3]. Furthermore, efficient and uniform solutions to the SAT problem by using systems from TDC(3) [1] and from TSC(8) [3] have been given. Recently, the last result has been improved to SAT ∈PMCT SC(3) [6]. Problem 1. Assuming P=NP, in the framework of tissue P systems with cell division/cell separation, a frontier of the tractability is obtained when passing from communication rules with length 1 to communication rules with length at most 3. Does passing from 1 to 2, amounts to passing from non–efficiency to efficiency? Frontiers of Membrane Computing 203 Conjecture: NP ∪co-bfNP ⊆PMCT DC(2). (B) The role of direction in communication rules Next, we deal with complexity aspects of tissue P systems with cell divison/celll separation where only symport or antiport rules are allowed. We have: P= PMCT DA(1) =PMCT SA(1), and NP ∪co −NP ⊆PMCT DA(3) ∩PMCT SA(3). Thus, assuming P=NP, a first frontier between efficiency and non-efficiency is obtained in the above framework when passing from communication rules with length 1 to communication rules with length at most 3. Problem 2. What about the complexity classes PMCT DA(2),PMCT SA(2), PMCT DS(k)and PMCT SS(k), for all k≥1? Conjecture: P =PMCT SA(2), and for all k≥1, P=PMCT SS(k). If this conjecture is true, then passing from symport rules to antiport rules with length at least three, amounts to passing from non–efficiency to efficiency, in the framework of tissue P systems with cell separation. (C) The role of the environment Classical tissue P systems have a special alphabet associated with the environment, whose elements appear at the initial configuration of the system, in an arbitrary large amount of copies. What may happen if this property is removed, that is, if the alphabet associated to the environment were empty? We use a “hat” to indicate the case when the environment is initially empty. Recently, have been proved that, for each k≥1, PMCT DC(k)= PMC[ T DC(k)[5], that is, in the framework of tissue P systems with cell division the role of the environment is not relevant from the complexity point of view. Conjecture: For each k≥1, P=PMC[ T SC(k). If this conjecture is true, then in the framework of tissue P systems with cell communication the following holds: (a) passing from separation rules to division rules (length at least three) amounts to passing from non–efficiency to efficiency; and (b) the environment provides a new borderline of efficiency. References 1. D. D´ıaz, M.A. Guti´errez, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science, 404 (2008), 76–87. 2. R. Guti´errez-Escudero, M.J. P´erez-Jim´enez, M. Rius-Font: Characterizing tractability by tissue-like P systems. Membrane Computing. 10th International Workshop, WMC 2009, Curtea de Arge¸s, August 2009. Revised Selected and Invited Papers, LNCS 5957, Springer, Berlin, 2010, 289–300. 3. L. Pan, M.J. P´erez-Jim´enez: Computational complexity of tissue–like P systems. Journal of Complexity, 26 (2010), 296–315. 204 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. 4. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Tissue P systems with cell division. International Journal of Computers, Communications & Control, 3 (2008), 295–303. 5. M.J. P´erez-Jim´enez: The role of the environment in tissue P systems with cell division. Submitted, 2012. 6. M.J.P´erez-Jim´enez, P. Sos´ık: Improving the efficiency of tissue P systems with cell separation. Submitted, 2012. 12 Time-Free Solutions to Hard Computational Problems Matteo Cavaliere National Center for Biotechnology, CNB - CSIC, Madrid, Spain [email protected] P systems are usually synchronized, a unique clock marks the time for all components, and in each time unit each component evolves (usually, in the maximal parallel manner). In time-free (and clock-free) systems, this strong assumption is removed. Up to now, the efficiency of P systems was not investigated also for this case. Required Notions: Time-free P system, synchronization, recognizing P system, uniform/semi-uniform solution. 12.1 Motivations Living cells have division rates that are highly heterogeneous (even in identical environmental conditions), consequence of their stochastic gene expression, [1]. Therefore, the possibility of programming living cells should not assume the presence of uniform replication rates. Ideally, one should construct “cellular computers” whose functioning is independent of cellular division rates. We suggest that such problem can be addressed in the framework of membrane computing by extending the notion of time-freeness ([4]) to the idea of semi-uniform solutions of computational problems based on membrane divisions ([3]). 12.2 Timed Recognizer P Systems From [4] we recall the notion of timed P system. Atimed P system Π(e) can be constructed by adding to a (standard) P system Πa time-mapping e:R−→ N, where Ris the set of rules of Π. The time-mapping specifies the execution times for the rules. A timed P system Π(e) works in the following way. We suppose to have an external clock that marks time-units of equal length (called steps), starting from step 0, when the system is present in its initial configuration. Frontiers of Membrane Computing 205 At each step, all the rules that can be started, in each region, and for each membrane have to be started (maximal parallel and nondeterministic use of rules). When a rule ris started at step j, then its execution terminates (the rule is completed) at step j+e(r), that means the rule lasts e(r)steps. The objects and the membranes produced by the rule are available – can be subject of other rules – only starting from the step j+e(r)+1.When a rule ris started, then the occurrences of symbol-objects and the membrane subject by this rule cannot be anymore subject of other rules. A computation halts when no rule can be started in any region and there are no rules in execution (such configuration is called halting). We say that the computation halts in ksteps, if the external clock marks step kwhen the last rules of the computations are completed. From [3] we recall the notion of recognizer P systems. A decision problem X is a pair (IX, ΘX) where IXis a countable language over a finite alphabet (the elements are called instances), and ΘXis a predicate (a total boolean function) over IX. Arecognizer P system is a P system such that: (i) the working alphabet contains two distinguished elements yes and no; (ii) all computations halt; and (iii) if Cis a computation of the system, then either object yes or object no (but not both) must have been released into the environment, and only when the last rules of the computation have been completed. We extend recognizer P systems by proposing the following timed variant: a recognizer timed P system is a timed P system with properties (i), (ii), (iii) above. In recognizer timed P systems, we say that a computation is an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the environment associated with the corresponding halting configuration. 12.3 Time-Free Solutions to Decision Problems Let X= (IX, ΘX) be a decision problem. Let Π=Πu, u ∈IX, a (countable) family of recognizer P systems. We say that the family Πis sound (with respect to X) if for each instance of the problem u∈IXsuch that there exists an accepting computation of Πu, we have ΘX(u) = 1. We say that the family Πis complete (with respect to X) if for each instance of the problem u∈IXsuch that ΘX(u) = 1, every computation of Πuis an accepting computation. We say that the family Πis polynomially bounded if there exists a polynomial function p(n) such that, for each u∈IX, all computations in Πuhalts in, at most, p(|u|) steps. We can now formalize the original motivations: A solution to a problem is timefree if its soundness, its completeness and its polynomial bound do not depend on the time of execution associated to the rules of the constructed systems. 206 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. We say that the family Πis time-free sound (with respect to X) if, for any time-mapping e, the family Πe=Πu(e), u ∈IX, is sound with respect to X. We say that the family Πis time-free complete (with respect to X) if, for any time-mapping e, the family Πe=Πu(e), u ∈IX, is complete with respect to X. We say that the family Πis time-free polynomially bounded if, for any timemapping e, the family Πe=Πu(e), u ∈IX, is polynomially bounded. We can now adapt the definition of semi-uniform solutions, as given in [3], and consider time-free semi-uniform solutions. Let X= (IX, ΘX) a decision problem. We say that Xis solvable in a timefree polynomial time by a family of recognizer P systems Π=Πu, u ∈IX, if the following are true: •the family Πis polynomially uniform by a Turing machine; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Πufrom the instance u∈IX. •the family Πis time-free polynomially bounded. •the family Πis time-free sound and time-free complete (with respect to X). We say that the family Πis a time-free semi-uniform solution to the decision problem X. In other words, to provide a time-free solution one must construct the family of systems Πin polynomial time (sequential time by deterministic Turing machines) and the constructed family must be “fast” (polynomially bounded), sound and complete with respect to the considered problem X, and these properties must be independent of the execution time of the rules (i.e., they must be fulfilled independently of the time-mapping considered). The definition of time-free semi-uniform solution captures the problem informally discussed in the Motivations. The basic question consists in finding a class of membrane systems for which it is possible to construct time-free semi-uniform solutions to hard computational problems. The simplest possibility is to transform the solutions already present in literature into time-free solutions (e.g., could the solution given in [2] be adapted to become a time-free solution?). Another interesting problem is to find classes of membrane systems that are powerful enough to solve complex problems, but simple enough to allow an automatic (i.e., algorithmic) checking of their time-freeness. References 1. M.B. Elowitz, J. Levine, E.D. Siggia, P.S. Swain: Stochastic gene expression in a single cell. Science, 297 (2002), 5584. 2. Gh. P˘aun: P systems with active membranes: Attacking NP complete problems. Journal of Automata, Language and Combinatorics, 6 (2001), 75–90. 3. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, A. Romero–Jim´enez, D. Woods: Complexity – membrane division, membrane creation. Chapter 12 in [5], 302–336. Frontiers of Membrane Computing 207 4. M. Cavaliere, D. Sburlan: Time-independent P systems. Membrane Computing. Int. Workshop WMC 2004, Milan, Italy, 2004 (G. Mauri et al., eds.), LNCS 3365, Springer, 2005, 239–258. 5. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford Univ. Press, 2010. 13 Fypercomputations Gheorghe P˘aun Institute of Mathematics of the Romanian Academy Bucharest, Romania, and Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] Following the model of hypercomputation (computing beyond the “Turing barrier”), we propose here the term fypercomputation to name the research area of “solving polynomially problems which are (at least) NP-complete”. Some ideas from/for MC are mentioned. Required Notions: membrane division, membrane creation, hypercomputing, SN P system, reaction system, accelerated P system Looking for ideas which would lead to computing devices able to compute “beyond the Turing barrier” is already a well established research area of computing theory; such devices are said to be able of doing hypercomputations. It is also a dream and a concern of computability to speed-up computing devices; a name was proposed in [7] (the idea was further elaborated in [8]) for the case when this leads to polynomial solutions to problems known to be (at least) NP-complete: fypercomputing – with the initial Fcoming from “fast”. In short: fypercomputing means going polynomially beyond NP. The model we have in mind is that of hypercomputations, already with a large literature (we only mention the recent survey from [10]). More than a dozen of ideas were proposed and proved to reach the goal of computing “beyond Turing”: oracles (already considered by Turing), introducing real numbers in the device, accelerating the functioning of machines, using ingredients of an analogical nature and so on. Many of these ideas can probably lead not only to hypercomputations, but also to fypercomputations, both in MC and in other frameworks. Although not clustered under a good name, such as hypercomputation (there are periodical meetings dedicated to this research direction), there also are many 208 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. papers which can be placed under the flag of fypercomputing. They exploit ideas from physics, such as [9], propose analogical computations, such as [1]. Also the area of DNA computing is full of such ideas. The literature of membrane computing abounds in papers dealing with fypercomputations. In most cases, polynomial solutions to NP-complete problems – often, also of PSPACE-complete problems – are obtained, by making use of a space-time trade-off, with the space obtained during the computation, by means of operations inspired from biology. The most investigated operations of this kind are membrane division (with variants: separation, budding, etc.) and membrane creation. Further two similar ideas were also explored. The first one is based on string replication (see [3] for details), the second one is that of considering arbitrarily large pre-computed resources (see, e.g., [6]), but the last idea is only briefly investigated so far. Issues related to the conditions to be imposed to the given pre-computed resources should be further considered. Three more ideas, essentially different from the previous ones, were proposed in [8] and need additional research efforts. (1) The first candidate is the acceleration, an old one in computer science: a “clever” computing device learns from its own functioning; after performing a step in a time unit, it performs better for the second step, which is completed in half of the time necessary for the first step – and so on, at each step halving the time with respect to the previous step. If the first step takes one time unit, then the second one takes 1/2 time units, the third one 1/4 and so on, hence in two time units the computation ends. Important: we have here two clocks, an internal one, of the machine, and an external one, of the observer. The internal clock is faster and faster, so that the computation ends in two time units measured by the external clock, that of the observer/user. Accelerated Turing machines can solve the halting problem, hence they compute what usual Turing machines cannot. See references in [2], where the idea is extended to P systems: starting from the biological observation that “smaller is faster” and using membrane creation rules to create “faster reactors” (inner membranes), in an unbounded hierarchy, one can obtain P systems which “compute the uncomputable”. This trick can be used also in complexity, but we have to be cautious: we accelerate in order to get a speed-up... In two (external) time units we solve any problem, whatever complex it is. A way to make the things interesting is to accelerate only parts of a P system, thus having several levels of time speed. For instance, we can accelerate only (i) some elementary membranes, or (ii) only some rules (a given rule takes one time unit for the first application, half for the second application, and so on), or (ii) to have “accelerated objects” (the descendants of an object react faster than the father object, irrespective which are the rules which act on them and irrespective of the membranes where they are). Precise definitions should be found and their usefulness explored. Frontiers of Membrane Computing 209 (2) The previous ideas suggest the following speculation. We mentioned that we have (at least) two clocks, an external one, of the observer (or of the higher membranes in the structure) and the local clock(s), of the accelerated element, membrane, rule, object. Always, the inner clock is (much) faster than the external one, it performs sometimes an exponential number of steps while the external one only ticks once. We can then imagine that the inner time is orthogonal to the external time, hence the time has a 2D structure: the observer only senses one dimension of time, but certain “processors” can run along the other dimension, doing computations at-no-time for the observer. This looks very much as using oracles. Again, good definitions have to be found and explored. (3) One further idea, proved in [8] to lead to fypercomputations comes from the recently introduced reaction systems (we call them R systems) – see [4], [5]. One of the crucial postulates of R systems concerns the fact that one works with ωmultisets: an object either is not present, or it is present in arbitrarily many copies. This assumption can be extended also to P systems. More exactly, we consider P systems which contain certain distinguished elementary membranes, whose objects are present in arbitrarily many copies (for instance, if an object ais introduced from outside in such a membrane, then inside the membrane it immediately becomes aω). In [8], such a system is called ωP system and it is proved that SAT can be solved (in a uniform way) in a polynomial time by an ωP system. The construction in [8] uses cooperative rules; we do not know whether the result can be improved by imposing the restriction to use only non-cooperative rules. References 1. J.J. Arulanandham, C.S. Calude, M.J. Dinneen: Balance machines: computing = balancing. Aspects of Molecular Computing, 2004, LNCS 2950, Springer, 2004, 148– 161. 2. C.S. Calude, Gh. P˘aun: Bio-steps beyond Turing. BioSystems, 77 (2004), 175–194. 3. J. Castellanos, Gh. P˘aun, A. Rodriguez-Pat´on: Computing with membranes: P systems with worm-objects. Proc. IEEE 7th. Intern. Conf. on String Processing and Information Retrieval, SPIRE 2000, La Coruna, Spain, 2000, 64–74. 4. A. Ehrenfeucht, G. Rozenberg: Basic notions of reaction systems, Proc. DLT 2004, LNCS 3340, Springer, 2004, 27–29. 5. A. Ehrenfeucht, G. Rozenberg: Reaction systems. Fundamenta Informaticae, 75 (2007), 263–280. 6. T.-O. Ishdorj, A. Leporati: Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources. Natural Computing, 7 (2008), 519–534. 7. Gh. P˘aun: Membrane computing at twelve years. Back to Turku. Proc. UC 2011, Turku, Finland, June 2011, LNCS 6714, Springer, 2011, 36–37. 8. Gh. P˘aun: Towards “fypercomputations” (in membrane computing), LNCS 6714, Springer, 2011, 36–37. 210 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. 9. V. Putz, K. Svozil: Can a computer be “pushed” to perform faster-than-light? Proc. UC10 Hypercomputation Workshop “HyperNet 10”, Univ. of Tokyo, June 22, 2010. 10. A. Syropoulos: Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer, 2008. 14 Numerical P Systems Cristian Ioan Vasile1, Ana Brˆandu¸sa Pavel1, Ioan Dumitrache1, Gheorghe P˘aun2 1Department of Automatic Control and Systems Engineering Politehnica University of Bucharest, Romania {cvasile, apavel, idumitrache}@ics.pub.ro 2Institute of Mathematics of the Romanian Academy Bucharest, Romania, and Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] Extensions of numerical P systems motivated by using such systems in robot controlling are mentioned and problems occurring in this framework are formulated. Required Notions: numerical P system, complexity, promoters-inhibitors, catalyst Numerical P systems are a class of computing models (introduced in [5]; see also Chapter 23.6 of [6]) inspired both from the cell structure and economics: numerical variables evolve in the compartments of a cell-like structure by means of so-called production–repartition programs. The variables have a given initial value and the production function is usually a polynomial, whose value for the current values of variables is distributed among variables in the neighboring compartments according to the “repartition protocol”. In this way, the values of variables evolve; all positive values taken by a specified variable are said to be computed by the P system. These systems were recently used in a series of papers (see references in [1]) for implementing controllers for mobile robots; in this framework the P systems work in the computing mode: an input is introduced in the form of the values of some variables and an output is produced, as the value of other variables. Furthermore, in the robot control context, the so-called enzymatic numerical P systems were introduced and used, [2], [3], [4]. Such systems correspond to catalytic P systems Frontiers of Membrane Computing 211 in the “general” membrane computing: a program is applied only if the value of the associated enzyme is strictly greater than the smallest value of any variable involved in the production polynomial. Enzyme variables are not consumed or produced by the rules which they catalyze, but can be changed by the rules for which they do not act as catalysts. Therefore, their values can evolve during the computational process. Tissue numerical P systems are also considered in [8], with parallel use of programs. If in each membrane, at each step, we use a maximal set of programs (programs are selected nondeterministically, and a set of programs is applied only if it is maximal, no further program can be added to it in such a way that the new set is still applicable). Two possibilities appear: (i) a variable can appear only in one production function, and this is the only restriction in choosing (nondeterministically) the programs to apply in a step, and (ii) if two or more programs which are enabled at a computation step, i.e., they satisfy the condition imposed by the associated enzymes, share variables in their production functions, then they will all use the current values of those variables (we denote this with allP). A large variety of classes of numerical P systems appears in this way: (1) enzymatic or non-enzymatic, (2) deterministic or nondeterministic, (3) sequential, all-parallel, one-parallel, (4) used in the generating, computing, accepting mode; further variants can be added. By combining all these, a plethora of classes of numerical P systems appear. We do not recall here the definition of numerical P systems, with or without enzyme control, but we refer the reader to the papers mentioned above. We only mention that the family of sets of numbers N+(Π) computed by numerical P systems Πwith at most mmembranes, production functions which are polynomials of degree at most n, with integer coefficients, with at most rvariables in each polynomial, is denoted by N+Pm(polyn(r), seq), m ≥1, n ≥0, r ≥0, where the fact that we work in the sequential mode (in each step, only one program is applied) is indicated by seq. If one of the parameters m, n, r is not bounded, then it is replaced by ∗. (Both in N+(Π) and in N+Pm(polyn(r), seq), the superscript + indicates the fact that as the result of a computation we only consider positive natural numbers, zero excluded. If any value is accepted, then we remove the superscript +.) When tissue systems are used, we write NtPm(polyn(r), α, β). Here are a few results from [5] and [8]. Theorem 1. NRE =N+P8(poly5(5), seq) = N+P7(poly5(6), seq) = NP7(poly5(5), enz, seq) = NtP∗(poly1(11), enz, oneP) = NP254(poly2(253), enz, allP, det). Whether or not the parameters appearing in these results are optimal or not is an open problem. Only a few of the many cases mentioned above were so far investigated, the other ones wait for research efforts. In particular, we have seen that enzymes improve the universality results in terms of the complexity of used polynomials, both in the cell-like case and the 218 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. The type systems can be used in defining more general and simpler rules for P systems. For example, if N1and N2are some basic types, by considering a set of typed objects V={X1:N1,X2:N1,X3:N1,A:N2}, the evolution rules of the form Xi→Xj,Xj→A, 1 ≤i≤3, 1 ≤j≤3, can be replaced by rules of a more general form: 1. N1→N1(any object of type N1can evolve in any object of type N1); 2. N1→N2(any object of type N1can evolve in any object of type N2). 16.4 Behavior Equivalence Behavior equivalence is an important concept in biology needed for analyzing and comparing the organs behavior. For example, an artificial organ is the functional equivalent of the natural organ, meaning that both behave in a similar manner up to a given time; e.g. the artificial kidney has the same functional characteristics as an “in vivo” kidney. Recently, it is shown in [7] that the vas deferens’ of the human, canine, and bull are equivalent in many ways, including histological similarities. In [6] are presented different methods for comparing protein structures in order to discover common patterns. In membrane computing, two P systems are considered to be equivalent whenever they have the same input/output behavior. Such an equivalence does not take care of the evolution of the two systems. What does it mean that two P systems have equivalent (timed) behavior? Defining several equivalences, we offer flexibility in selecting the right one when verifying biological systems and comparing them. When a P system can be replaced in a context with another one such that the observed behavior is the same? References 1. O. Agrigoroaiei, G. Ciobanu: Reversing computation in membrane systems. Journal of Logic and Algebraic Programing, 79 (2010), 278–288. 2. O. Agrigoroaiei, G. Ciobanu: Rule-based and object-based event structures for membrane systems. Journal of Logic and Algebraic Programing, 79 (2010), 295–303. 3. O. Agrigoroaiei, G. Ciobanu: Quantitative causality in membrane systems. Proc. Twelfth International Conference on Membrane Computing, Fontainebleau, 2011, 53– 63. 4. B. Aman, G. Ciobanu: Typed membrane systems. Int. Workshop on Membrane Computing, WMC 2009, LNCS 5957, Springer, 2010, 169–181. 5. G. Berry, G. Boudol: The chemical abstract machine. Theoretical Computer Science, 96 (1992), 217–248. 6. I. Eidhammer, I. Jonassen, W. Taylor: Structure comparison and structure patterns. Journal of Computational Biology, 7 (2000), 685–716. 7. D.E. Leocadio, A.R. Kunselman, T. Cooper, J.H. Barrantes, J.C. Trussell: Anatomical and histological equivalence of the human, canine, and bull vas deferens. The Canadian Journal of Urology, 18 (2011), 5699–5704. Frontiers of Membrane Computing 219 8. Gh. P˘aun: Some open problems collected during 7th BWMC. Proc. Seventh Brainstorming Week on Membrane Computing, 2009, vol. 2, 197–206. 9. B. Russell: The Principles of Mathematics, vol. I, Cambridge University Press, 1903. 10. J. Wells: The essence of principal typings. LNCS 2380, Springer, 2002, 913–925. 17 Kernel P Systems Marian Gheorghe Department of Computer Science, University of Pite¸sti, Romania Department of Computer Science, University of Sheffield, UK [email protected] The issue of a common generalization of several classes of P systems is proposed, and some basic ideas towards such a goal are presented. Required Notions: tissue P system, P system with dynamic structure, regular expression Different variants of P systems have been used for specifying simple algorithms [5, 2], classes of NP-complete problems [7] and various applications [6]. More specific classes of P systems have been recently considered for modeling some distributed algorithms and problems [8]. In many cases the evolution of the system investigated requires some specific behavior or the use of certain rules, maybe with some constraints, which are not always the same as the ones exhibited by the model in its initial definition. It helps in many cases to have some flexibility with the modeling approach, especially in the specification stage, as it shortens the model and makes it clearer. Although there is a powerful specification language, called P-lingua, with implementations for various variants of P systems [9], there is no unified framework that allows us to simulate, verify and test the behavior of the specified systems. In this respect, it is suggested here a kernel P system (kP system, for short) that, in the first stage, will be a low level specification language including the most used concepts from P systems. The generic structure of a kP system might be a graph-like structure as in tissue P systems. Such a model uses a set of symbols, labels of membranes, rules of various types and a certain strategy to run them against the multiset of objects available in each region. The rules in each compartment will be of two types: (i) object processing rules which transform and transport objects between compartments or exchange objects between compartments and environment, and (ii) system structure rules responsible for changing the system’s topology. Each rule has a guard, defined using activators and inhibitors in a general way. The execution strategy is defined such that maximally parallel or sequential manners are captured 220 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. and each compartment has its own strategy. Rewriting and communication rules based on promoters and inhibitors are considered together with a special set of symport/antiport rules. Additional features like membrane division, creation, dissolution, bond creation and destruction are used to deal with the system structure. The key concept of a compartment is first introduced and then the definition of a kP system. Definition 1. Given an alphabet A, of elements named objects, and an alphabet Lof labels, a compartment is a tuple C= (l, w0, Rσ), where l∈Lis the label of the compartment, w0is the initial multiset over A, and Rσdenotes “the DNA code”, i.e., the set of rules, denoted R, applied in this compartment and a regular expression, σ, over Lab(R), the labels of the rules of R. Definition 2. Akernel P system is a tuple kΠ = (A, L, IO, µ, C1, . . . , Cn), where Aand Lare, as in Definition 1, the alphabet of objects and the set of labels, respectively; IO is a multiset of objects from A, called environment;µdefines the membrane structure, which is a graph, (V, E), where Vare vertices, V⊆L (the nodes are labels of these compartments), and Eedges; C1, . . . , Cnare the n compartments of the system – the inner part of each compartment is called the region which is delimited by a membrane; the labels of the compartments are from Land initial multisets are over A. We first discuss various types of rules. It is assumed that the rules below belong to the same compartment, Ci, labeled li. Each rule might have a regular expression associated with. When a rule involves more than a compartment, then each compartment might have its own regular expression attached to it. RE(A∪¯ A) denotes the set of regular expressions over A∪¯ A; each such regular expression defines conditions involving promoters, elements from A, and/or inhibitors, elements from ¯ A. The interpretation of a regular expression g∈RE(A∪¯ A), associated with a rule, is that all the promoters appearing in gmust be present in the current multiset and none of the inhibitors must appear there. We call this regular expression, g,guard. A rule with such a guard is applicable when this is evaluated to true. A rule can have one of the following types: •rewriting and communication rule: x→y{g}, where x∈A+,y∈A∗, g∈RE(A∪¯ A); the right hand side, y, has the form y= (a1, t1). . . (ah, th), where aj∈Aand tj∈L, 1 ≤j≤h, is an object and a target (i.e., the label of a compartment), respectively; the target tjmust be either the label of the current compartment, li(more often ignored) or of an existing neighbor of it ((li, tj)∈E) or an unspecified one, ∗; otherwise, the rule is not applicable; if a target tjrefers to a label that appears more than once, then one of the involved compartments will be nondeterministically chosen; if tjis ∗, then the object ajis sent to a compartment arbitrarily chosen; •input-output rule, is a form of symport/antiport rule: (x/y){g}, where x, y ∈ A∗,g∈RE(A∪¯ A); xfrom the current region, li, is sent to the environment and yfrom the environment is brought into the current region; Frontiers of Membrane Computing 221 •system structure rules; the following types are considered: –membrane division rule: []li→[]li1. . . []lih{g}, where g∈RE(A∪¯ A); the compartment liwill be replaced by hcompartments obtained from li, i.e., the content of them will coincide with that of li; their labels are li1, . . . , lih, respectively; all the links of liare inherited by each of the newly created compartments; –membrane dissolution rule: []li→λ{g}; the compartment liwill be destroyed together with its links; –link creation rule: []li; []lj→[]li−[]lj{cg}; the current compartment li is linked to ljand, if more than one ljexists, then one of them will be nondeterministically picked up; cg, called compound guard, describes an expression li.g1op lj.g2, where g1, g2are regular expressions referring to compartments liand lj, respectively; op is either and or or, standing for either both guards are true or at least one is true. If one of the guards is empty then op is no longer used; a compound guard defines a Boolean condition across the two compartments; –link destruction rule: []li−[]lj→[]li; []lj{cg}; this is the opposite of link creation and means that compartments li, ljare disconnected; as usual, when more than a link, (li, lj)∈E, exists, then only one is considered by this rule; cg is a compound guard. The usual behavior of P systems requiring that rewriting and communication, and symport/antiport (input-output) rules are applied in a maximal parallel way (or sequentially in some cases), whereas membrane division, creation, dissolution rules and creation and destruction of links are executed one per membrane, will be considered in this context as well, but in a rather more general way. The main challenges of this approach are 1. a rigorous definition of the syntax and semantics of kP systems; 2. comparisons between (fragments) of kP systems and well-known variants of P systems; 3. establishing general algorithms to translate different classes of P systems into kP systems (similar to [1, 4]); 4. defining operational semantics for kP systems and providing implementations in model checkers, like Spin, Maude, similar to [3]. Further steps in developing this unified framework might consist of adding other useful modeling features like the possibility of defining rules and compartments using indexes, a certain concept of a module, various other semantics. It is intended to keep the kernel system as generic as possible such that some of the above mentioned extensions will be introduced in a rather syntactical manner allowing to map them into the basic variant, without additional semantics. Acknowledgement. This work was partially supported by project MuVet, Romanian National Authority for Scientific Research (CNCS, UEFISCDI) grant number PN-II-ID-PCE-2011-3-0688. 222 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. References 1. A. Alhazov, L. Pan, Gh. P˘aun: Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41 (2004), 111–144. 2. A. Alhazov, D. Sburlan: Static sorting P systems. In [6], 2006, 215–252. 3. O. Andrei, G. Ciobanu, D. Lucanu, A rewriting logic framework for operational semantics for membrane systems. Theoretical Computer Sci., 373 (2007), 163–181. 4. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, S. Tini: Membrane systems working in generating and accepting modes: Expressiveness and encodings. Membrane Computing, 11th International Conference, CMC2010, Jena, Germany, August 2010 (M. Gheorghe et al., eds), LNCS 6501, Springer, 2011, 103–118. 5. R. Ceterchi, C. Mart´ın-Vide: P systems with communication for static sorting. Pre- Proc. Brainstorming Week on Membrane Computing, Tarragona, February 2003 (M. Cavaliere et al., eds.), Technical Report no 26, Rovira i Virgili Univ., Tarragona, TR 26/03, URV, 2003, 101–117. 6. G. Ciobanu, Gh. P˘aun, M.J. P´erez-Jim´enez, eds.: Applications of Membrane Computing, Springer, 2006. 7. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez: A uniform family of tissue P systems with cell division solving 3-COL in a linear time. Theoretical Computer Science, 404 (2008), 76–87. 8. R. Nicolescu, M.J. Dinneen, Y.-B. Kim: Structured modelling with hyperdag P systems. Part A. Membrane Computing, Seventh Brainstorming Week, BWMC 2009, Sevilla, Spain, February 2009 (A.R. Guti´errez-Escudero at al., eds.), Universidad de Sevilla, 2009, 85–107. 9. The P-lingua Website: http://www.p-lingua/wiki/index.php/Main Page. 18 Bridging P and R Gheorghe P˘aun Institute of Mathematics of the Romanian Academy Bucharest, Romania, and Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] Some possibilities of bridging MC (P systems) and reaction systems are discussed, the basic idea being of importing ideas from a research area to another one. Required Notions: cell P system, multiset, reaction system, halting, fypercomputing Reaction systems (we call them R systems) form a recently introduced research area aiming to model the evolution of (bio)chemicals by means of (bio)reactions, Frontiers of Membrane Computing 223 in a framework based on the following two fundamental assumptions (we recall them in the formulation from [1]): The way that we define the result of a set of reactions on a set of elements formalizes the following two assumptions that we made about the chemistry of a cell: (i) We assume that we have the “threshold” supply of elements (molecules) – either an element is present and then we have “enough” of it, or an element is not present. Therefore we deal with a qualitative rather than quantitative (e.g., multisets) calculus. (ii) We do not have the “permanence” feature in our model: if nothing happens to an element, then it remains/survives (status quo approach). On the contrary, in our model, an element remains/survives only if there is a reaction sustaining it. With these postulates in mind, let us consider first some possibilities of passing from R systems to P systems. Moving from multisets, which are basic in P systems, to sets (actually, to multisets with an infinite multiplicity of their elements, called ωmultisets in Section 13) is a fundamental assumption, which changes completely the approach; for instance, we can no longer define computations with the result expressed in terms of counting molecules: the total set of molecules is finite, any molecule is either absent or present in infinitely many copies. However, as we have mentioned in Section 13, considering P systems with ω multisets leads in an easy way to fypercomputations. The second assumption of the reaction systems theory (no permanence of objects) looks easier to handle in terms of MC. The immediate idea is to simply remove (by a “deletion rule”) any element which does not evolve by means of a reaction; somewhat equivalently, if we want to preserve an object awhich is not evolving, we may provide a dummy rule for it, of the type a→a, changing nothing. Still, many technical problems appear in this framework. The presence of such dummy rules makes the computation endless, while halting is the “standard” way to define successful computations in MC. Moreover, the rules are nondeterministically chosen, hence the dummy rules can interfere with the “computing rules”. While the second difficulty is a purely technical one, the first one can be overpassed by considering other ways of defining the result of a computation in a P system, and there are many suggestions in the literature. We mention here three possibilities: (i) the local halting (the computation stops when at least one membrane in the system cannot use any rule), (ii) signal-objects (the result consists of the number of objects in a specified membrane at the moment when a distinguished object appears in the system), (iii) signal-events (the result consists of the number of objects in a specified membrane at the moment when a distinguished rule is used in the system). Such possibilities were considered in various papers in MC. Part of these possibilities are checked in [7] from where we recall the following result: 224 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. Theorem 2. Transition P systems of degree 2, using cooperative rules, without the permanence of objects, are computationally complete when the successful computations are defined by local halting or signal-objects. The same result holds true for symport/antiport P systems (of degree 2 and of weight 2) for the case of local halting. An interesting open problem in this framework is the case of catalytic P systems, known to be universal in the “permanence” assumption. The case of defining the result of a computation of symport/antiport P systems by means of signals – objects or events – also remains as an open problem. (Considering a priority relation on each set of rules can easily solve this problem.) The symport/antiport P system used in the proof of Theorem 2 [7] contains antiport rules of sizes (2, 1) and (1, 2), which is “large” for universality results in the case when objects are persistent. Can the size of rules be decreased also in the case discussed here? The R systems area has a series of notions of the dynamical systems type which were not too much investigated for P systems (time, events, modules, structure, causality, and so on), and this is also a promising direction of research. Let us now briefly explore the other direction, from P to R. The R systems are not meant to define computations, their behavior is deterministic, from a set of symbols we precisely pass to a unique set of symbols. However, starting from an R system, a “generative device” can be defined, based on passing from a configuration to another one (without input from the environment), provided that some nondeterminism is introduced in the R system functioning. Three possibilities of this kind were proposed in [7]: (i) working with tabled R systems, as in Lindenmayer systems (in each step, a table is used, nondeterministically chosen), (ii) considering also a finite multiplicity for some of the objects, and (iii) by introducing a general threshold kon the number of rules which can use the same molecule. All these three possibilities remain to be investigated: properties of the obtained computation graphs, possible links with computing devices from formal language and automata theory, influence of the introduced parameters (number of tables, threshold k), possible hierarchies. Of course, a general research topic is to find other ways of building a (string or graph) computing device in terms of R systems. A possible question is also the possibility to introduce membranes in the R systems area or other MC ingredients – thus getting a sort of PR systems. (An attempt of this kind is reported in [5], where so-called reaction automata are introduced, but these devices violates both postulates of R systems and use so many ingredients of P systems – multisets, parallelism, nondeterminism, halting – that they are just P automata with a new name.) Frontiers of Membrane Computing 225 References 1. A. Ehrenfeucht, G. Rozenberg: Basic notions of reaction systems, Proc. DLT 2004 (C.S. Calude et al., eds.), LNCS 3340, Springer, 2004, 27–29. 2. A. Ehrenfeucht, G. Rozenberg: Reaction systems. Fundamenta Informaticae, 75 (2007), 263–280. 3. A. Ehrenfeucht, G. Rozenberg: Events and modules in reaction systems. Theoretical Computer Sci., 376 (2007), 3–16. 4. A. Ehrenfeucht, G. Rozenberg: Introducing time in reaction systems. Theoretical Computer Sci., 410 (2009), 310–322. 5. F. Okubo, S. Kobayashi, T. Yokomori: On the properties of languages classes defined by bounded reaction automata. Theoretical Computer Sci., in press. 6. Gh. P˘aun: Towards fypercomputations (in membrane computing). LNCS, Springer, to appear. 7. Gh. P˘aun, M.J. P´erez-Jim´enez: Towards bridging two cell-inspired models: P systems and R systems. Theoretical Computer Sci., to appear. 19 P Systems and Evolutionary Computing Interactions Gexiang Zhang School of Electrical Engineering Southwest Jiaotong University, Chengdu, P.R. China [email protected] Problems related to the so-called membrane algorithms (actually, distributed evolutionary computing, with the distribution controlled by means of membranes, as well as with other MC ingredients used) are mentioned, both in the direction of improving the optimization techniques and in looking for more complex/practical applications. Required Notions: evolutionary computing, cell P system, active membranes, membrane algorithm As a relatively young branch of natural computing, MC has gone through thirteen years of intensive research involving areas of theoretical computer science as well as applications in various fields, including systems biology, graphics, linguistics, parallel and distributed computing. However, these applications, in terms of varieties and types, are relatively small compared to a very broad range of applications of evolutionary computing. A natural question would be, whether some combinations of these two models might benefit from the large scope of applications evolutionary computing has already shown so far, and the rigorous and sound theoretical development membrane systems have proved for all its variants. 226 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. The possible interplay between MC and evolutionary computation may produce three kinds of research topics: Membrane-inspired evolutionary algorithms (MIEAs): Since membrane computing was initiated in 1998, a large number of theoretical results, such as various variants of membrane systems and their computational power and efficiency came forth [1]. On the one hand, the way MC is extended into real-world applications is not easy to be addressed and represents an ongoing issue. On the other hand, the hybridization of different computing techniques is an attractive research topic in the area of evolutionary computing, due to a better performance than their counterpart approaches. What can the young paradigm of MC bring to evolutionary computation? Fortunately, MIEAs, formerly called membrane algorithms [2, 3], create a bridge between MC and various real-world applications. MIEA concentrates on generating new evolutionary algorithms for solving optimization problems by using the hierarchical or network structures of membranes and rules of P systems, and the concepts and principles of meta-heuristic search methodologies [3, 4]. The comparative analysis of dynamic behaviors of an instance of MIEAs shows the appropriate combination of MC and evolutionary computation can produce a better capability to balance exploration and exploitation [5], which are two contradictory factors directly related to the performance of an optimization algorithm. Until now, MIEAs have been studied in conjunction with cell P systems with a fixed membrane structure and by considering an evolutionary computing approach as a subalgorithm put inside a membrane [1, 6, 7]. Further research topics are listed below. 1. Consider further combinations of features that make full use of the characteristics of both MC models and evolutionary computing, such as the consideration of cell P systems with active membranes, tissue P systems and population P systems. 2. Usually, in an MIEA an evolutionary algorithm is used as a subalgorithm placed inside a membrane. This idea can be extended. A membrane structure can be used as a framework of the organization of several different types of evolutionary operators, as shown in [8], or several distinct kinds of evolutionary mechanisms, such as a genetic algorithm, evolutionary programming, evolution strategy, differential evolution and particle swarm optimization. Furthermore, the flexible communication rules can be used at the level of genes, instead of at the level of individuals shown in [6, 4]. 3. The single-objective problems are usually involved in the investigations reported in the literature. The framework of P systems can offer better population diversity in MIEAs, hence further work can turn to solve problems in a complex environment, such as multi-objective, dynamic, peaked optimization problems, and with/without constraints, to check whether P systems can bring a better performance to evolutionary algorithms. 4. More real-world application problems, such as power system optimization, software/hardware co-design and vehicle route plan, can be solved by using MIEAs. Frontiers of Membrane Computing 227 5. A deep performance analysis and evaluation of MIEAs is necessary to reveal the roles of P systems played in the hybrid optimization algorithms, on the basis of the previous work [5]. Automated design of membrane computing models (ADMCMs): The automated synthesis of some types of MC models or of a high level specification of them is envisaged to be obtained by applying various evolutionary algorithms. ADMCMs aim to circumvent the programmability issue of membrane based models for complex systems [9]. This is quite a complex problem as it involves a great number of parameters (rules, objects, combination of rules) and many semantics associated with P systems. Membrane evolutionary algorithms (MEAs): MEAs will focus on implementing evolutionary algorithms within a P system environment in order to take advantage of the parallelism and distribution of MC, given that recent investigations are studying the implementation of P systems on parallel or multi-core hardware platforms. An important challenge for any of the above research developments will be to apply them to complex real life systems. Acknowledgement. This work was supported by the National Natural Science Foundation of China (61170016), the Program for New Century Excellent Talents in University and the Project-sponsored by SRF for ROCS, SEM. References 1. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. 2. T.Y. Nishida: Membrane algorithm with brownian subalgorithm and genetic subalgorithm. International Journal of Foundations of Computer Science, 18 (2007), 1353– 1360. 3. G.X. Zhang, C.X. Liu, H.N. Rong: Analyzing radar emitter signals with membrane algorithms. Mathematical and Computer Modelling, 52 (2010), 1997–2010. 4. G.X. Zhang, J.X. Cheng, M. Gheorghe: A membrane-inspired approximate algorithm for traveling salesman problems. Romanian Journal of Information Science and Technology, 14 (2011), 3–19. 5. G.X. Zhang, C.X. Liu, M. Gheorghe: Diversity and convergence analysis of membrane algorithms. Proc. of the Fifth International Conference on Bio-Inspired Computing: Theories and Application, 2010, 596–603. 6. G.X. Zhang, M. Gheorghe, C.Z. Wu: A quantum-inspired evolutionary algorithm based on P systems for Knapsack Problem. Fundamenta Informaticae, 87 (2008), 93–116. 7. J.X. Cheng, G.X. Zhang, X.X. Zeng: A novel membrane algorithm based on differential evolution for numerical optimization. International Journal of Unconventional Computing, 7 (2011), 159–183. 8. G.X. Zhang, M. Gheorghe, Y.Q. Li: A membrane algorithm with quantum-inspired subalgorithms and its application to image processing. Natural Computing, 2012, DOI: 10.1007/s11047-012-9320-2. (published online) 234 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. conclusion. Once the number of “elements” in the experiment is decreasing, most of our methods to investigate properties of those “elements” become hard/impossible to describe/investigate. Obviously this statement is rather broad and there are some techniques such as FRET analysis that look at discrete events/elements, but we claim that the majority of the current bio-molecular techniques do require large multiplicities of the “element” investigated. The aforementioned fact has to be understood by the researcher looking to model/simulate cells. It describes the state of the research tools in that area. The modeler can help that particular area by offering better insight into the sub-cellular processes through simulation and prediction. One could immediately point out that since we have a “technological” problem (as stated before) which is precluding us to gain insight into the “discrete” processes, then how can one hope to simulate the sub-cellular mechanisms. The answer is two-fold: (1) cells prove to respond mostly in the same fashion to similar stimuli, meaning that the inherent stochasticity of these systems does not “break” the response pathways (making the simulation from this perspective “easy” as we need to simulate the “important” events, not all the noise associated with the gene regulation mechanisms and their stochasticity); (2) even if we do not know a mechanism, once a model is built based on our best knowledge and we see it diverging from reality in a specific point, we know where to start investigating for other processes/reactions. There is also a philosophical motivation to using P systems for a cell simulator: P systems were defined to capture the compartmentalized structure of the eukaryotic cells, and indeed this compartmentalization could prove one of the best features of a cell simulator. Furthermore: due to the current biomolecular techniques involving large multiplicities for a species the simulation techniques in the area focussed on ordinary differential equations (ODE) as continuous mathematics both has powerful tools and are easily implemented. But we claim that a continuous mathematics approach in this area of sub-cellular simulation may not be the best approach as some processes have been seen to behave discretely, and in several pathways we can see the multiplicity of some multiprotein complexes appear in very small numbers (below 10). In such cases a discrete simulation technique such as Gillespie’s algorithm would be preferable to the simulators based on ODE [4]. Incidentally we have also defined a discrete simulation technique in [2] which was repeatedly improved (see references in [5]) and was lately named NWA with memory. The motivation behind the NWA algorithm was simple: we wanted a discrete mathematics based simulation technique that would be faster than Gillespie’s algorithm. 22.1 Brief Description for Current Cellular Models and Simulators In order to plausibly model the biochemistry of life, individual biochemical interactions need to occur asynchronously over different lengths of time. The model relies on the law of mass action. The law states that reaction rate is directly proportional to the number of reactants available in the system. In other words, the time Frontiers of Membrane Computing 235 required to execute a rule in the cell is dependent on the number of its reacting species. We note that the rule application is not considered to be instantaneous; the kinetics that are giving the reaction speed model the time required by the molecules involved in the rule to couple together (if the reaction is of second order or higher) as well as the time required for the actual reaction to take place. The law of mass action gives us the power to temporally describe the evolving configurations of our system. To understand the asynchrony of rule execution, we need to discuss the kinetic rates pertaining to the law of mass action. The kinetics of a chemically reactive system are often described as concentration-based values. This is common for the types of experiments used to derive the rates, typically involving enormous populations (millions) of cells. The cells are often lysed as a large population, molecules are measured in terms of light intensity and data are given as concentrations of species across cell population. These values can be averaged across the cell population, yielding concentrations per cell. We rely on these values to fit our models, but the values are derived from entire cell populations instead of individual cells. Hence, the interesting phenotypic, biochemical and physiological characteristics of individual cells can be sometimes overgeneralized (or lost) in lieu of the behavior of the majority of the cells in the population. Some labs employ techniques to measure single-cell dynamics. For example, interesting results/models on p53 have been reported in [7], where it is shown that individual cells undergo not dampened oscillations, as reported in [1], but each individual cell instead exhibits a different numbers of oscillations. The average behavior for the cell population appeared to be dampened, but individual cells did not behave this way. We are collaborating with Mark DeCoster’s biomedical laboratory from Louisiana Tech University in order to study single cell data via a high-speed imaging system. It is our hope that future collaborations will help unlock some of the secrets behind Fas-induced apoptosis. Regardless of whether data comes from large cell populations or single cell dynamics, we, as modelers, must remain vigilant and build the best models with the data available to us. Using the law of mass action and discrete kinetic constants we can define the Waiting Time (WT) of a reaction in the P system. The WT is a value assigned to each reaction, signifying the next timepoint for a single execution of the reaction. As molecular multiplicities will change throughout a simulation, from one configuration to the next, so will the WTs of reactions utilizing those molecules. We used a min-heap for sorting reactions, where the top of the heap is the reaction with the smallest WT – i.e., the next reaction to be executed. However, we need to use nonstandard methods for maintaining the heap, due to the asynchrony of the rules and the sharing of reactants. These nonstandard methods are similar to those proposed by Gibson and Bruck [3] in their modification to the Gillespie algorithm. To clarify, when a rule is applied, multiple nodes can have changes to their WT, since the multiplicities of particular species of the system have changed. These species can be shared over multiple reactions. Hence, multiple WT potentially 236 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. can fail the min-heap property throughout the tree simultaneously at each new configuration. In order to handle this, we use heap maintenance methods similar to those proposed by Gibson and Bruck [3] in their modification of the Gillespie algorithm. 22.2 Improving the Simulators The following “open problems” are mostly for the simulator developed by our group but should be relevant for other simulators as well. 1. increase the stochasticity at the level of the heap by applying a modified Monte Carlo simulation technique for the first 3 levels of the heap (the fastest 7 reactions), 2. faster implementation such as using C rather than C++ or Java, 3. GPU implementation of the simulator for parallel simulations and identifying “decision points” in the pathway; also running the same model several times could identify the minority from the majority (this information could be lost in an ODE framework for simulation), 4. bigger and better models for sub-cellular mechanisms, 5. using Manca’s Log-gain theory to gather stoichiometric data to be used in simulations [6], 6. implementing the simulation framework as a plug-in in CoPasi for broader dissemination and usage. Acknowledgements. The author acknowledges support from UEFISCDI – PNIITE 92/2010. References 1. R.L. Bar-Or, R. Maya, L.A. Segel, U. Alon, A.J. Levine, M. Oren: Generation of oscillations by the p53-Mdm2 feedback loop: A theoretical and experimental study. Proc. Natl. Acad. Sci., USA, 97 (2000), 11250–11255. 2. S. Cheruku, A. P˘aun, F.J. Romero-Campero, M.J. P´erez-Jim´enez, O.H. Ibarra: Simulating FAS-induced apoptosis by using P systems. Progress in Natural Science, 17 (2007), 424–431. 3. M.A. Gibson, J. Bruck: Efficient exact stochastic simulation of chemical systems with many species and many channels. Journal of Physical Chemistry A, 104 (2000), 1876–1889. 4. D.T. Gillespie: Exact stochastic simulation of coupled chemical Reactions,” The Journal of Physical Chemistry, vol. 81, no. 25, 1977, pp. 2340–2361. 5. J. Jack, A. P˘aun: Discrete modeling of biochemical signaling with memory enhancement. LNBI Transactions on Computational Systems Biology, 5750 (2009), 200–215. 6. V. Manca: The metabolic algorithm for P systems: Principles and applications. Theoretical Computer Science, 404 (2008), 142–155. 7. G. Lahav, N. Rosenfeld, A. Sigal, N. Geva-Zatorsky, A.J. Levine, M.B. Elowitz, U. Alon: Dynamics of the p53-Mdm2 feedback loop in individual cells. Nature Genetics, 36 (2004), 147–150. Frontiers of Membrane Computing 237 23 P Systems for Computational Systems and Synthetic Biology Marian Gheorghe1,2, Vincenzo Manca3, Francisco-Jos´e Romero-Campero4 1Department of Computer Science, University of Pite¸sti, Romania 2Department of Computer Science, University of Sheffield, UK [email protected] 3Department of Computer Science, University of Verona, Italy [email protected] 4Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, Spain [email protected] Deterministic and stochastic P system models are discussed in the context of specifying fairly complex biological systems; their usage for systems and synthetic biology is also presented. Required Notions: metabolic P systems, dynamical inverse problem, stochastic P systems, Gillespie algorithm, systems biology, synthetic biology The approaches based on P systems aiming to provide coherent descriptions of fairly complex biological systems are either deterministic or stochastic [5]. Two such variants are discussed below, but some more variants of the above mentioned types of P systems are available in the current literature, see [15] and Sections 21 and 22 of this paper. Metabolic P systems (MP systems for short) were introduced in 2004 as a particular kind of P systems devised for modeling metabolic processes [7]. Their main goal consists in solving dynamical inverse problems (DIPs) by means of discrete systems. A general algorithm, called Log-Gain Stoichiometric Stepwise Regression (LGSS), providing MP solutions to DIPs was obtained, in a systematic way, by integrating finite difference recurrent equations, least square method, stepwise regression, and related Fisher tests, within a suitable linear algebra framework where solutions can be expressed as ordinary and tensor products among matrices [11]. A MATLAB implementation of LGSS was developed by Luca Marchetti [12]. Many successful applications of MP theory to biological dynamics were developed, starting from classical examples (Lotka-Volterra, Brusselator, Mitotic Oscillator) [10]. Presently, the two main applications under investigation concern the insulin-glucose dynamics in diabetes pathologies and genetic expression in a kind of breast cancer (in cooperation with endocrinologists and clinicians in Italy, Verona and in USA, Detroit). A synthetic description and references is given by Vincenzo Manca in [8, 9]. 238 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. Stochastic P systems, SP system for short, are rule-based discrete and stochastic multicompartmental systems used as abstract structures to model stochastic cellular systems [14]. The key difference between the original P systems and SP systems consists in a stochastic constant that is specifically associated with each rule. This constant is used to determine in a specific state or configuration of the system the probability of applying the corresponding rule and the time elapsed between rule applications according to Gillespie’s stochastic simulation algorithm [6]. SP systems allow the incremental and parsimonious design of models by providing modelers with the feature of modularity explicitly [4]. A P system module consists of a finite set of rewriting rules that may contain some free variables in their objects, labels and stochastic constants. Modules can be arranged in libraries so they can be reused to define the rewriting rules of different models. In this respect, modules act like macros that get expanded once the corresponding module variables are instantiated with specific molecular species names, numerical values for the stochastic constants and compartment names. A variant of SP systems, lattice population P systems [18], allow modelers to represent multi-cellular systems with specific geometries by distributing copies of given individual stochastic P systems over the points of a finite geometrical lattice. SP systems have been implemented in the software tool for the specification, simulation, analysis and optimization of systems and synthetic biology models, Infobiotics workbench [3]. These systems have been used to model signal transduction pathways [13, 1], bacterial gene regulation [17], bacterial populations [16], metapopulations [2] and synthetic biology problems [19]. Membrane computing has made very significant contributions in certain areas of computer science and has produced some impact with respect to a number of applications. It remains a challenge to show how it copes with complex applications, especially in systems and synthetic biology. Some of these challenges are listed below: •identify more complex systems to be specified by one of the variants of P systems described above or presented in [15]; •extend the current variants with additional features in order to cope with more complex applications; •create a repository of illustrative biological case studies; •develop additional complementary approaches that help analyzing biological systems – data sensitivity analysis, property data extraction and verification, hierarchies of languages allowing to map P system specifications into biochemical reactions; •implement adequate tools exploiting the latest technologies and create benchmark problems to assess them. Frontiers of Membrane Computing 239 Acknowledgement. M.G.’s work was partially supported by project MuVet, Romanian National Authority for Scientific Research (CNCS, UEFISCDI) grant number PN-II-ID-PCE-2011-3-0688. References 1. D. Besozzi, P Cazzaniga, S. Cocolo, G. Mauri, D. Pescini: Modelling diffusion in a signal transduction pathway: the use of virtual volumes in P systems. Int. J. Found. Comput. Sci., 22 (2011), 89–96. 2. D. Besozzi, P Cazzaniga, D. Pescini, G. Mauri: Modelling metapopulations with stochastic membrane systems. BioSystems, 91 (2008), 499–514. 3. J. Blakes, J. Twycross, F.J. Romero-Campero, N. Krasnogor: The Infobiotics Workbench: an integrated in silico modelling platform for Systems and Synthetic Biology. Bioinformatics, 27 (2011), 3323–3324. 4. H. Cao, F.J. Romero-Campero, S. Heeb, M. C´amara, N. Krasnogor: Evolving cell models for systems and synthetic biology. Syst. Synth. Biol., 4 (2010), 55–84 5. M. Gheorghe, V. Manca, F.J. Romero-Campero: Deterministic and stochastic P systems for modelling cellular processes. Natural Computing, 9 (2010), 457–473. 6. D.T. Gillespie: Stochastic simulation of chemical kinetics. Annual Review of Physical Chemistry, 58 (2007), 35–55. 7. V. Manca: The metabolic algorithm for P systems: Principles and applications.Theoretical Computer Science, 404 (2008), 142–155. 8. V. Manca: Metabolic P systems.Scholarpedia, 6 (2010), 9273. 9. V. Manca: Fundamentals of metabolic P systems. Chapter 6 in [15], 475–498. 10. V. Manca L. Bianco, F. Fontana: Evolutions and oscillations of P systems: Theoretical considerations and application to biological phenomena. Proc. WMC 2004, Milan, Italy, June 2004, LNCS 3365, Springer, 2005, 63–84. 11. V. Manca, L. Marchetti: Solving dynamical inverse problems by means of metabolic P systems. BioSystems, to appear. DOI:10.1016/j.biosystems.2011.12.006. 12. L. Marchetti, V. Manca: A methodology based on MP theory for gene expression analysis. Proc. CMC 2011, Fontainebleau, France, August 2011, LNCS 7184, Springer, 2012, 300–313. 13. A. P˘aun, M.J. P´erez-Jim´enez, F.J. Romero-Campero: Modeling signal transduction using P systems. Proc. WMC 2006, Leiden, The Netherlands, July 2006, LNCS 4361, Springer, 2006, 100–122. 14. Gh. P˘aun, F.J. Romero-Campero: Membrane computing as a modeling framework: cellular systems case studies. Proc. Formal Methods for Computational Biology, 8th Intern. School, Bertinoro, Italy, June 2008 (M. Bernardo et al, eds.), LNCS 5012, Springer, 2008, 168–214. 15. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford Univ. Press, 2010. 16. F.J. Romero-Campero, M.J. P´erez-Jim´enez: A model of the quorum sensing system in Vibrio fischeri using P systems. Artificial Life, 14 (2008), 95–109. 17. F.J. Romero-Campero, M.J. P´erez-Jim´enez: Modelling gene expression control using P systems: The Lac Operon, a case study. BioSystems, 91 (2008), 438–457. 18. F.J. Romero-Campero, J. Twycross, M. C´amara, M. Bennett, M. Gheorghe, N. Krasnogor: Modular assembly of cell systems biology models using P systems. Int. J. Found. Comput. Sci., 20 (2009), 427–442. 240 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. 19. J. Smaldon, F.J. Romero-Campero, F. Fern´andez Trillo, M. Gheorghe, C. Alexander, N. Krasnogor: A computational study of liposome logic: towards cellular computing from the bottom up. Syst. Synth. Biol., 4 (2010), 157–179. 24 Biologically Plausible Applications of SN P Systems for an Explanation of Brain Cognitive Functions Adam Obtulowicz Institute of Mathematics, Polish Academy of Sciences, Warsaw, Poland [email protected] Some conjectures about the possibility of using SN P systems and extension of them for modeling features of the brain (such as learning, modularity) are formulated. Required Notions: spiking neuron, SN P system, learning The (hierarchical) clustering (scene segmentation in particular) and binding (feature integration) problem solution in cortical neural networks together with cortical subnetworks realizing Radial Basic Functions (briefly RBFs) represent, among others, the cognitive functioning of brain. Recently, various network models of clustering, binding problem solution, and realization of RBFs in cortical networks have been proposed, where spiking neural networks are the most biologically plausible models, see [16], [17], [2], [3], [12], [14], [15], and [11] for a review. The main common feature of these models is Hebbian learning which provides their biological evidence. On the other hand, a transformation of an idea of Hebbian learning from a framework of spiking neural networks to a framework of SN P systems (cf. [10]) has been proposed in [8]. Thus, one formulates the following question: Do SN P systems provide biologically plausible mathematical models of brain cognitive functions? We approach the question and an answer to it by the following discussion of conjectures and setting open problems. Papers [5], [9] contain promising applications of SN P systems for solving topic problems related to some cognitive brain functions. But biological evidence of these applications seems problematic because Hebbian learning procedures approach is not considered for them. On the other hand, the Hebbian learning modeled by SN P systems with only input neurons and one output neuron presented in [8] and solution of XOR problem by spiking neural networks equipped with a Hebbian learning procedure and with Frontiers of Membrane Computing 241 only three input neurons and one output neuron described in [4] gives rise to the following conjecture: Conjecture 1. There exists a learning problem, understood as in [8], whose output is an SN P system solving XOR problem. If we compare precise timing of spikes approach for spiking neural networks to the number of spikes approach for SN P systems, then the latter seems coarse and hence less biologically plausible than the spiking neural network approach. On the other hand, the precise timing of spikes approach for spiking neural networks is less biologically plausible than probabilistic spiking neural networks because a relevant amount of noise is contained in the behavior of neurons (cf. [7]). Therefore it is worth to initiate a research of probabilistic SN P systems. The view that human mind is “massively modular” (cf. [6], [13]) argued by massively parallel functioning of brain neural network modules, gives rise to a question of approaching these massive modularity and massive parallelism of mind and brain by application of a concept of a network of communicating SN P systems equipped with Hebbian learning procedures, respectively. The SN P systems constituting that network could correspond to brain network modules realizing simultaneously various cognitive functions, respectively. On the other hand, since SN P systems seem more coarse with respect to an approach to time than spiking neural networks with precise timing of spikes, like, e.g., in [2], we propose the following conjecture. Conjecture 2. A biologically plausible modularity of brain could be represented (modeled)by the following hybrid constructs: 1. a two-level construct of a spiking super-neural P system which is an SN P system whose neurons are superneurons, i.e., multi-layer spiking neural networks with a precise timing of spikes like, e.g., in [2], 2. a three-level construct of a spiking sub-super-neural P system which is a spiking super-neural P system as above, where the neurons of superneurons are P systems approaching neurons as cells which produce and transport copies of molecules between electrically charged membranes. The construct in 1) gives rise to multi-layer spiking networks which could learn themselves like in [2] their modular structure of spiking super-neural P systems and hence which could explain emergence of cognitive capabilities of brain. It is worth to discuss the above constructs with regard to the possibility of their molecular implementation which is suggested by recent findings outlined in [1]. References 1. A. Bandyopadhyay, D. Fujita, R. Pati: Architecture of a massively parallel processing nano-brain operating 100 billion molecular neurons simultaneously. International Journal of Nanotechnology and Molecular Computation, 1 (2009), 50–80. 242 M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, eds. 2. S.M. Bohte: Spiking Neural Networks. Professorschrift, Leiden University, 2003. 3. O. Booij: Temporal Pattern Classification using Spiking Neural Networks. M.Sc. Thesis, Amsterdam University 2004. 4. O. Booij, Hieu tat Nguyen: A gradient descent rule for spiking neurons emitting multiple spikes. Applications of Spiking Neural Networks (S.M. Bohte, J.N. Kok, eds.), Information Processing Letters, Amsterdam, 2005. 5. R. Ceterchi, I.A. Tomescu: Spiking neural P systems–a natural model for sorting networks. Proc. Sixth Brainstorming Week on Membrane Computing (D. Diaz-Pernil et al., eds.), Sevilla, February 4–8, 2008, RGNC Report 01/2008, Fenix Editora, Sevilla, 2008, 93–105. 6. D. Geary: The Origin of Mind: Evolution of Brain, Cognition, and General Intelligence. American Psychological Association 2005. 7. W. Gerstner: Population dynamics of spiking neurons: Fast transients, asynchronous states, and locking. Neural Computation, 12 (2000), 43–89. 8. M.A. Guti´erez-Naranjo, M.J. P´erez-Jim´enez: A spiking neural P systems based model for Hebbian learning. Proc. 9th Workshop on Membrane Computing (P. Frisco et al., eds.), Edinburgh, July 28–31, 2008, 189–207. 9. M. Ionescu, D. Sburlan: Some applications of spiking neural P systems. Proc. 8th Workshop on Membrane Computing (Eleftherakis et al., eds.), Thessaloniki, June 25–28, 2007, 383–394. 10. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fund. Inform., 71 (2006), 279–308. 11. A. Kasi´nski, F. Ponulak: Comparison of supervised learning methods for spike time coding in spiking neural networks. Int. J. Appl. Math. Comput. Sci., 16 (2006), 101– 113. 12. A. Knoblauch, G. Palm: Scene segmentation by spike synchronization in reciprocally connected visual areas. II: Global assemblies and synchronization on larger space and time scales. Biol. Cybern., 87 (2002), 168–184. 13. K. MacDonald, D. Chiappe: Review of [6] in Human Ethology Bulletin, 21 (2006), 14–18. 14. B. Meftah, A. Benyettou, O. Lezoray, W. Qingxiang: Image clustering with spiking neuron network. World Congress on Computational Intelligence, International Joint Conference on Neural Networks, Hong-Kong, 2008. 15. S.C. Moore: Back-propagation in Spiking Neural Networks. M.Sc. Thesis, University of Bath 2002, http://www.simonchristianmoore.co.uk/Thesis4.html. 16. T. Natschl¨ager, B. Ruf: Spatial and temporal pattern analysis via spiking neurons. Network: Comp. Neural Systems, 9 (1998), 319–332. 17. B. Ruf: Computing and Learning with Spiking Neurons–Theory and Simulation. Doctoral Thesis, Technische Universit¨at Graz, 1998. Frontiers of Membrane Computing 243 25 Computer Vision Daniel D´ıaz-Pernil1, Miguel A. Guti´errez-Naranjo2 1CATAM Research Group, Dept. of Applied Mathematics I University of Sevilla, Spain [email protected] 2Research Group on Natural Computing, Dept. of Computer Science and AI University of Sevilla, Spain [email protected] Some possibilities to employ MC techniques in computer vision (especially in thresholding, smoothing, homology theory) are discussed. Required Notions: array grammar, array-rewriting P system, cell and tissue P systems Computer vision is probably one of the challenges for computer scientists in the next years. From a biological point of view, vision is an extremely complex process involving the transformation of the light energy into a signal which leaves the eye by way of the optic nerve and arrives to the brain, where it is interpreted. From a computational point of view, a digital image is a function from a two dimensional surface which maps each point form the surface to a set of features as bright or color. In MC, there is a large tradition in handling information structured as two dimensional objects (see, e.g., [2, 3, 9, 16]). The main motivation for these studies is to bring together P systems and picture grammars. From a technical point of view, arrays are two-dimensional objects placed inside the membranes as strings are one-dimensional objects in the model of P systems with string objects [13]. In [3], the model of array-rewriting P systems was presented on the basis of the transition P systems: Rules are of type A → B(tar) where Ais the array to be rewritten, Bis the new one, and tar ∈ {here, in, out}indicates the place of the picture after the substitution has been made. Recently, a new research line has been open by applying well-known MC techniques for solving problems from digital imagery. For example, segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics. Segmentation has shown its utility, for example, in bordering tumors and other pathologies or computer-guided surgery. In [5, 8, 10, 11] we can find several approaches to this problem with MC techniques. Other problems, as thresholding [4] or smoothing [18] have also been considered in the framework of MC. Special attention deserves [14], where the symmetric dynamic programming stereo (SDPS) algorithm [15] for stereo matching was implemented by using simple P modules with duplex channels. A different approach to computer vision can also be obtained from computational topology. In particular, algebraic topology provides techniques and algorithms for handling digital images from a topological point of view. Recently, the