Abstract
In a previous paper we have shown that membrane systems with controlled mobility are able to solve a \(\Pi_2^\mathrm{P}\) complete problem. Then, an enriched model with forced endocytosis and forced exocytosis enables us to move to the fourth level in the polynomial hierarchy, the model having \(\Sigma_4^\mathrm{P} \cup \Pi_4^\mathrm{P}\) as lower bound. In this paper we study the computability power of this model (using forced endocytosis and forced exocytosis), and determine the border condition for achieving computational completeness: 4 membranes provide Turing completeness, while 3 membranes do not. Moreover, we show that the restricted division operation (which is crucial in achieving the \(\Sigma_4^\mathrm{P} \cup \Pi_4^\mathrm{P}\) lower bound) does not provide computational completeness. However, Turing completeness can be achieved with pairs of operations (exocytosis, inhibitive endocytosis) and (inhibitive exocytosis, endocytosis) by using 4 membranes. Finally, we present some computability results expressing that membrane systems which use the operations of restricted division, restricted exocytosis and inhibitive endocytosis cannot yield computational completeness.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aman, B., Ciobanu, G.: Solving a Weak NP-complete Problem in Polynomial Time by Using Mutual Mobile Membrane Systems. Acta Informatica 48(7-8), 409–415 (2011)
Aman, B., Ciobanu, G.: Mobility in Process Calculi and Natural Computing. Springer (2011)
Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory (1989)
Freund, R., Păun, G.: On the Number of Non-terminal Symbols in Graph-Controlled, Programmed and Matrix Grammars. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol. 2055, pp. 214–225. Springer, Heidelberg (2001)
Krishna, S.N., Aman, B., Ciobanu, G.: Solving the 4QBF Problem in Polynomial Time by Using the Biological-Inspired Mobility (preprint)
Krishna, S.N., Ciobanu, G.: On the Computational Power of Enhanced Mobile Membranes. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 326–335. Springer, Heidelberg (2008)
Krishna, S.N., Ciobanu, G.: Computability Power of Mobility in Enhanced Mobile Membranes. In: Löwe, B., Normann, D., Soskov, I., Soskova, A. (eds.) CiE 2011. LNCS, vol. 6735, pp. 160–170. Springer, Heidelberg (2011)
Krishna, S.N., Ciobanu, G.: A \(\Sigma_2^P \cup \Pi_2^P\) Lower Bound Using Mobile Membranes. In: Holzer, M. (ed.) DCFS 2011. LNCS, vol. 6808, pp. 275–288. Springer, Heidelberg (2011)
Krishna, S.N., Păun, G.: P Systems with Mobile Membranes. Natural Computing 4, 255–274 (2005)
Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall (1967)
Păun, G.: P Systems with Active Membranes: Attacking NP-Complete Problems. Journal of Automata, Languages and Combinatorics 6(1), 75–90 (2001)
Păun, G., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press (2010)
Pérez-Jiménez, M.J., Riscos-Núñez, A., Romero-Jiménez, A., Woods, D.: Complexity-Membrane Division, Membrane Creation. In: [12], pp. 302–336
Rozenberg, G., Salomaa, A. (eds.): The Mathematical Theory of L Systems. Academic Press (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krishna, S.N., Aman, B., Ciobanu, G. (2012). On the Computability Power of Membrane Systems with Controlled Mobility. In: Cooper, S.B., Dawar, A., Löwe, B. (eds) How the World Computes. CiE 2012. Lecture Notes in Computer Science, vol 7318. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30870-3_63
Download citation
DOI: https://doi.org/10.1007/978-3-642-30870-3_63
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30869-7
Online ISBN: 978-3-642-30870-3
eBook Packages: Computer ScienceComputer Science (R0)