Scientific context and motivation
The main concepts of the project are computability, complexity and causality in the context of membrane systems, related process calculi, Petri nets and other formalisms. Computability and complexity are cornerstones of theoretical computer science, while causality is an issue without a generally accepted formal characterization.
Membrane computing [Paun02, Paun10] is a well-established and successful research field which deals with parallel and nondeterministic computing models inspired by cell biology. It was initially developed by Gh. Păun in 1998, and in 2003 was identified by Thomson Institute for Scientific Information as a “fast emerging research front in computer science”. Membrane systems are complex hierarchical structures with a flow of materials and information which underlies their functioning, involving parallel application of rules, communication between membranes and membrane dissolution. A “computation” is performed in the following way: starting from an initial structure, the system evolves by applying the rules in a nondeterministic and maximally parallel manner. The maximally parallel way of using the rules means that in each step we apply a maximal multiset of rules, namely a multiset of rules such that no further rule can be added to the multiset. A halting configuration is reached when no rule is applicable.
Process calculi (or process algebras) are a family of related approaches to the formal modelling of concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, and synchronizations between a collection of independent agents or processes. They also provide algebraic laws that allow process expressions to be manipulated and analysed, and permit formal reasoning about equivalences between processes (e.g., using bisimulation). Some examples of process calculi are: -calculus, ambient calculus, brane calculi. We refer here to the formal description of mobility in computer science. The first formalism in computer science able to describe mobility is the -calculus [Milner89], followed by ambient calculus [Cardelli98]. In contrast with other formalisms for mobile processes such as the -calculus based on the notion of communication, the ambient calculus is based on the notion of movement. An ambient is a named location, and represents a unit of movement. Ambients mobility is controlled by the capabilities in, out, and open; the mobile ambients describe the migration of processes between certain boundaries. A biologically-inspired version of ambient calculus is given by bioambients [Regev04] and several brane calculi [Cardelli04]. On the other hand, systems of mobile membranes [KrishnaPaun05] represent other formalisms with mobility in the framework of membrane computing.
Petri nets are bipartite directed graphs used in the modelling, analysis and verification of parallel systems by using both graphical and algebraic tools [Reisig98]. Places indicate the location of resources (tokens), whereas transitions are actions which can occur depending on local conditions related to the availability of resources. When a transition occurs it consumes resources from its input places and produces tokens in its output places.
All these domains are represented by a strong scientific community, with an ample scientific activity consisting of conferences (such as CMC, ETAPS, CONCUR, ICALP, UC, CiE) and journals with high impact factors (Theoretical Computer Science, Acta Informatica, Information and Computation, Natural Computing, Journal of Logic and Algebraic Programming, BioSystems). Our research group has a tradition of publishing in these venues, and we continue to target them for the dissemination of our project results.
The new problems we intend to study are as follows.
We start from the question whether concurrency strictly extends sequentiality in terms of computability power and computational efficiency. According to the existing results (e.g., [Cardelli98, Paun10] and our recent work in [Aman09, Ciobanu11]), it seems that process calculi and membrane computing with mobility do not increase the computability power of Turing machines. Focusing on computational efficiency, we want to show that concurrent systems (in particular biologically inspired calculi) can solve hard problems (e.g. SAT and QBF) in shorter time than sequential systems. We intend to study the computability power of concurrent systems in order to find a minimal set of ingredients (number of compartments and involved resources) for which the formalisms are Turing complete. Reachability is usually undecidable in Turing complete formalisms (e.g, -calculus, mobile ambients). Nevertheless, interesting fragments have been studied which are expressive enough to model all computable functions, but for which reachability turns out to be decidable. Following this research line, we plan to study the reachability in several fragments of process calculi and biological inspired calculi in which mobility is the key ingredient (e.g., mobile membranes). We made an initial approach towards reachability in [Aman07].
Existing approaches [Aceto96, Busi07] to causality in our general context mainly consist of enriching existing semantics with labels or timing information, either of which is then used to keep track of links between resources or processes. This assumes that the evolution of the system can be observed in its entirety. We propose to obtain the causal links between the components of the system without the introduction of external ingredients, thus in a simpler manner. We have performed the first steps towards this goal by associating two different types of event structures to membrane systems in [Agrigoroaiei10].
Main Objectives
Computability
Finding minimal ingredients and boundary conditions for Turing completeness of (fragments of) the studied formalisms.
Studying (the decidability of) reachability in membrane systems and several fragments of biological inspired process calculi in which mobility is a key ingredient.
Decidability of other important properties (such as emptiness, boundedness, safety and liveness).
Existent results present in literature (e.g., [Busi06, Busi09]) concern mainly reachability and boundedness in ambient calculus and brane calculi. Starting from these results we aim to extend them to other families of complex systems. Moreover, there is a lack of results concerning the above mentioned characteristics which we intend to remedy.
Complexity
Studying complexity classes (e.g., NP and PSPACE) for mobile membrane systems and biologically inspired calculi.
Solving hard problems (e.g., SAT and QBF) in polynomial time by using mobile membrane systems and biologically inspired calculi.
There are papers in the field of natural computation, namely in membrane computing [Paun10], defining new complexity classes and solving NP-complete problems in polynomial time by using biologically inspired operations like polarizations, membrane division, symport/antiport communication, etc. The formal approach in membrane computing is mainly based on formal languages, and many proofs use matrix grammars (with appearance checking). However, there is no explicit presentation on whether/how process calculi and Petri nets solve hard problems.
Causality
Obtaining causality from the semantics of the studied formalisms without adding external ingredients such as labels/timers.
Refining existing notions of causality beyond the relations derived from a simple temporal ordering (event structures).
The notion of causality is described in the existent literature in various modes, ranging from that given by temporal ordering [Sassone96] to that given by certain “markers” placed on events [Aceto96, Busi07]. There exists no general definition of causality for a family of formalisms like those in the general context of this project. Moreover, we intend to move the focus of the notion of causality from transition events to states (comprised of resources, objects, and so on). We aim to also link causal information with reachability (see our previous paper [Agrigoroaiei09]).
Method and approach
We detail the methods and approaches we employ at the level of each major objective.
1. Calculability In order to study the computability power of a system or calculi fragment we use formal languages and automata (for more details on the techniques employed in the field, see [Paun10]). We also use classifications such as the Lindenmayer families of languages, and encodings of Turing machines and their restrictions [Hopcroft79, Salomaa73]. We will start by using matrix grammars (as we have done in [Aman09] for mobile membrane systems) to determine iteratively some minimality conditions on the number of ingredients required to achieve Turing completeness. Once we determine such conditions, we can start mapping border conditions for separating complete fragments of the studied formalisms. We intend to adapt some of the techniques presented in the Handbook of Membrane Computing [Paun10] to our formal approach. We have started to investigate reachability problems in mobile membranes by the method of reduction to a known problem in Petri nets as in [Aman07]. We thus have a starting point for the study of reachability in (fragments of) biologically inspired calculi.
2. Complexity One of the applications of membrane computing is the ability to solve intractable problems in polynomial time. The existing variants with active membranes have several powerful features like polarizations, dissolution, evolution and communication rules, as well as non-elementary membrane division. We intend to investigate the use of simpler variants which uses only elementary membrane division and mobility of membranes. The complexity classes P, NP, coNP, L, NL, PP, PSPACE [Papadimitriou95, Garey79] have been studied in the context of active membranes (chapter 12 of [Paun10]). In this chapter it is also stated that there is no known variant of membrane systems with active membranes that can solve NP-complete problems in polynomial time without using any of the features of polarizations, non-elementary division and dissolution (and this is mentioned as an open problem). Moreover, no variant of polarizationless systems with active membranes has gone beyond the first level of the polynomial hierarchy using only the operations of communication and elementary membrane division. We intend to prove that simple variants using only elementary division and mobility (endocytosis and exocytosis) can solve intractable problems in polynomial time. This is the starting point for further analysis concerning the complexity power added by various features. We will consider both uniform and semi-uniform solutions, inspired by the notion of uniformity introduced in [Borodin77] for Boolean circuits.
3. Causality We use operational and denotational semantics [Nielson92] and notions of trace theory [Diekert97]. Event structures have also been extensively used to characterize causality in concurrent systems and Petri nets [Nielsen81]. Our starting idea is to use the temporal order of event structures as a weaker form of causality. Another starting angle is that of causal automata [Gunawardena92] which is more appropriate to membrane systems and biologically inspired calculi. Between event structures and causal automata, synchronization trees (possibly enhanced with additional causal information [Froschle07]) offer a midline approach with respect to the degree of abstraction of the studied system. We mention here a useful tool for membrane systems [Agrigoroaiei11] developed by our group which allows the encoding of hierarchical information at the level of rule application. This encoding has already allowed us to characterize a form of causality for a flat membrane system and to automatically extend it at a multiple membrane system in [Agrigoroaiei10].
As underlined throughout the project proposal, our group has already started investigations on all three main objectives. The results obtained are promising and have already been published in reputable journals or presented at established conferences. We can state that the risk of not reaching the proposed objectives is low. We consider that one of the strengths of our project proposal is that it is based on three related research lines. If one of the objectives will be difficult to reach, we can approach it from the direction of one of the other research lines.
Impact, relevance, applications
Of more immediate interest is the impact of the dissemination of the results. We first note that there already exists an international workshop called “MeCBIC: Membrane Computing and Biologically Inspired Process Calculi”, organized by the project proponent. This workshop is, in 2011, at its fifth edition and has brought together researchers working in membrane computing, in biologically inspired process calculi (ambients, brane calculi, etc.) and in other related fields to present recent results and to discuss new ideas concerning such formalisms, their properties and relationships. This shows the scientific community’s interest in tackling such research directions as presented in the project proposal. The workshop’s visibility can be seen in the fact that the proceedings of each edition have been published in Electronic Notes in Theoretical Computer Science and in Electronic Proceedings in Theoretical Computer Science. Moreover, selected papers from the last two editions will be published in 2011 in the well known journal Theoretical Computer Science.
As stated in section C1, our research group has a tradition of publishing in journals with high impact factors (Theoretical Computer Science, Acta Informatica, Information and Computation, Natural Computing, Journal of Logic and Algebraic Programming, BioSystems) and of presenting papers at important conferences (CMC, ETAPS, CONCUR, ICALP, UC, CiE). These are some of the target conferences and journals for the dissemination of our project results. We hope to achieve publication in even higher rated journals.
Bibliography
[Aceto96] L. Aceto, D. Murphy. Timing and Causality in Process Algebra. Acta Informatica, vol.33, 317-350, 1996.
[Agrigoroaiei09] O. Agrigoroaiei, G. Ciobanu. Dual P systems. Lecture Notes in Computer Science, vol. 5391, 95–107, 2009.
[Agrigoroaiei10] O. Agrigoroaiei, G. Ciobanu. Rule-based and object-based event structures for membrane systems. Journal of Logic and Algebraic Programming, vol. 79, 295 - 303, 2010.
[Agrigoroaiei11] O. Agrigoroaiei, G. Ciobanu. Flattening the Transition P Systems with Dissolution. Lecture Notes in Computer Science, vol. 6501, 53-64, 2011.
[Aman07] B. Aman, G. Ciobanu. On the Reachability Problem in P Systems with Mobile Membranes. Lecture Notes in Computer Science, vol.4860, 113-123, 2007.
[Aman09] B. Aman, G. Ciobanu. Simple, Enhanced and Mutual Mobile Membranes. Transactions on Computational Systems Biology XI, LNBI vol.5750, 26-44, 2009.
[Borodin77] A. Borodin. On Relating Time and Space to Size and Depth. SIAM Journal of Computing, vol 6(4), 733-744, 1977.
[Busi06] N. Busi. Deciding Behavioural Properties in Brane Calculi, Lecture Notes in Computer Science, vol. 4210, 17-31, 2006.
[Busi07] N. Busi. Causality in membrane systems, Lecture Notes in Computer Science, vol. 4860, 160–171, 2007.
[Busi09] N. Busi, G. Zavattaro. Deciding reachability problems in Turing-complete fragments of Mobile Ambients, Mathematical Structures in Computer Science, vol. 19(6), 1223-1263, 2009.
[Cardelli04] L. Cardelli. Brane Calculi. Interactions for biological membranes. Lecture Notes in BioInformatics, vol. 3082, 257-278, 2004.
[Cardelli98] L. Cardelli, A. Gordon. Mobile Ambients. Foundations of Software Science and Computation Structure, Lecture Notes in Computer Science vol. 1378, 140-155, 1998.
[Ciobanu11] G. Ciobanu, S. N. Krishna: Enhanced Mobile Membranes: Computability Results. Theory of Computing Systems, vol. 48(3), 715-729, 2011.
[Cohen04] J.E. Cohen. Mathematics is Biology’s Next Microscope, Only Better; Biology is Mathematics’ Next Physics, Only Better. PLoS Biology, vol.12, e439, 2004.
[Diekert97] V. Diekert, Y. Metivier, Partial Commutation and Traces. Handbook of Formal Languages, Vol. 3, Beyond Words. Springer-Verlag, Berlin,1997.
[Froschle07] S. B. Fröschle, S. Lasota. Causality versus true-concurrency. Theoretical Computer Science, vol. 386, 169-187, 2007.
[Garey79] M.R.Garey, D.S. Johnson. Computers and Intractability. A Guide to the Theory of NP completeness. W.H. Freeman and Company, New York, 1979.
[Gunawardena92] J. Gunawardena. Causal automata. Theoretical Computer Science, vol. 101, 265-288, 1992.
[Hopcroft79] J.E. Hopcroft, J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979.
[Jensen92] K. Jensen. Coloured Petri Nets; Basic Concepts, Analysis Methods and Practical Use. Vol. 1,2,3. Monographs in Theoretical Computer Science, Springer, 1992, 1994, 1997.
[KrishnaPaun05] S.N. Krishna, Gh. Păun. P Systems with Mobile Membranes. Natural Computing, vol. 4(3), 255-274, 2005.
[Milner89] R. Milner. Communication and Concurrency. Prentice Hall International, 1989.
[Nielson81] M. Nielson, G. D. Plotkin, G.Winskel. Petri Nets, Event Structures and Domains. Theoretical Computer Science, vol.13, 85–108, 1981.
[Nielson92] H. Nielson, F. Nielson: Semantics with Applications: A Formal Introduction. Wiley, 1992.
[Paun02] Gh. Păun. Membrane Computing. An Introduction. Springer, 2002.
[Paun10] Gh. Păun, G. Rozenberg, A. Salomaa (eds.). Handbook of Membrane Computing. Oxford University Press, 2010.
[Papadimitriou95] C.H. Papadimitriou: Computational Complexity. Addison-Wesley, 1995.
[Peterson81] J.L. Peterson. Petri Net Theory and the Modeling of Systems. Prentice-Hall, 1981.
[Regev04] A. Regev, E. M. Panina, W. Silverman, L. Cardelli, E Shapiro. BioAmbients: An Abstraction for Biological Compartments. Theoretical Computer Science, vol. 325, 141-167, 2004.
[Reisig98] W. Reisig, G. Rozenberg (Eds.). Lectures on Petri Nets. Lecture Notes in Computer Science, vol.1491–1492, Springer, 1998.
[Salomaa73] A. Salomaa: Formal Languages. Academic Press, 1973.
[Sassone96] V. Sassone, M. Nielsen, G. Winskel. Models for concurrency: towards a classification. Theoretical Computer Science, vol. 170, 297–348, 1996.
