Abstract
We first give a historical overview of the most important results obtained in the area of P systems and tissue P systems with symport/antiport rules, especially with respect to the development of computational completeness results improving descriptional complexity parameters. We consider the number of membranes (cells in tissue P systems), the weight of the rules, and the number of objects. Then we establish our newest results: P systems with only one membrane, symport rules of weight three, and with only seven additional objects remaining in the skin membrane at the end of a halting computation are computationally complete; P systems with minimal cooperation, i.e., P systems with symport/antiport rules of size one and P systems with symport rules of weight two, are computationally complete with only two membranes with only three and six, respectively, superfluous objects remaining in the output membrane at the end of a halting computation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alhazov, A., Freund, R.: P systems with one membrane and symport/antiport rules of five symbols are computationally complete. In: [25], pp. 19–28
Alhazov, A., Freund, R., Oswald, M.: Tissue P systems with antiport rules and a small number of symbols and cells. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 100–111. Springer, Heidelberg (2005)
Alhazov, A., Freund, R., Oswald, M.: Symbol/membrane complexity of P systems with symport/antiport rules. In: [12], pp. 123–146
Alhazov, A., Freund, R., Rogozhin, Y.: Computational power of symport/antiport: history, advances and open problems. In: [12], pp. 44–78
Alhazov, A., Freund, R., Rogozhin, Y.: Some optimal results on communicative P systems with minimal cooperation. In: [24], pp. 23–36
Alhazov, A., Margenstern, M., Rogozhin, V., Rogozhin, Y., Verlan, S.: Communicative P systems with minimal cooperation. In: [36], pp. 161–177
Alhazov, A., Rogozhin, Y.: Minimal cooperation in symport/antiport P systems with one membrane. In: [25], pp. 29–34
Alhazov, A., Rogozhin, Y., Verlan, S.: Symport/antiport tissue P systems with minimal cooperation. In: [24], pp, 37 – 52
Bernardini, F., Gheorghe, M.: On the power of minimal symport/antiport. In: Alhazov, A., Martín-Vide, C., Păun, G. (eds.) Pre-proceedings of Workshop on Membrane Computing, WMC-2003, Tarragona, July 17-22 (2003); Technical Report RGML 28/03, Universitat Rovira i Virgili, Tarragona, pp. 72–83 (2003)
Bernardini, F., Păun, A.: Universality of minimal symport/antiport: five membranes suffice. In: Martín-Vide, C., Mauri, G., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2003. LNCS, vol. 2933, pp. 43–45. Springer, Heidelberg (2004)
Calude, C.S., Păun, G.: Bio-steps beyond Turing. BioSystems 77, 175–194 (2004)
Freund, R., Lojka, G., Oswald, M., Păun, G. (eds.) Pre-proceedings of Sixth International Workshop on Membrane Computing, WMC6, Vienna, July 18–21 (2005)
Freund, R., Oswald, M.: GP systems with forbidding context. Fundamenta Informaticae 49, 81–102 (2002)
Freund, R., Oswald, M.: A short note on analysing P systems with antiport rules. Bulletin of the European Association for Theoretical Computer Science 78, 231–236 (2002)
Freund, R., Oswald, M.: P systems with activated/prohibited membrane channels. In: [44], pp. 261–268
Freund, R., Oswald, M.: Tissue P systems with symport/antiport rules of one symbol are computationally universal. In: [24], pp. 187–200
Freund, R., Păun, A.: Membrane systems with symport/antiport: universality results. In: [44], pp. 270–287
Freund, R., Păun, G.: aun: On deterministic P Systems. Manuscript (2003), available at, http://psystems.disco.unimib.it
Freund, R., Păun, G., Pérez-Jiménez, M.J.: Tissue-like P systems with channel states. In: [43], pp. 206–223; Theoretical Computer Science 330, 101–116 (2005)
Frisco, P.: About P systems with symport/antiport. In: [43], pp. 224–236
Frisco, P., Hoogeboom, H.J.: P systems with symport/antiport simulating counter automata. Acta Informatica 41, 145–170 (2004)
Frisco, P., Hoogeboom, H.J.: Simulating counter automata by P systems with symport/antiport. In: [44], pp. 288–301
Greibach, S.: Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science 7, 311–324 (1978)
Gutiérrez-Naranjo, M.A., Păun, G., Pérez-Jiménez, M.J.: Cellular Computing. Complexity Aspects. Fenix Editora, Sevilla (2005)
Gutierrez-Naranjo, M.A., Riscos-Núñez, A., Romero-Campero, F.J., Sburlan, D. (eds.) Proceedings of the Third Brainstorming Week on Membrane Computing, Sevilla, Spain, January 31 – February 4 (2005)
Ibarra, O.H.: On determinism versus nondeterminism in P systems. Theoretical Computer Science (to appear)
Ibarra, O.H., Woodworth, S.: On bounded symport/antiport P systems. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol. 3892, pp. 37–48. Springer, Heidelberg (2006)
Ibarra, O.H.: Some recent results concerning deterministic P systems. In: [12], pp. 24–25
Ibarra, O., Woodworth, S.: On symport/antiport P systems with one or two symbols. In: Pre-Proceedings of the Workshop on Theory and Applications of P Systems, Timişoara, September 26-27, pp. 75–82 (2005)
Ibarra, O.H., Woodworth, S., Yen, H., Dang, Z.: On symport/antiport systems and semilinear sets. In: [12], pp. 312–335
Kari, L., Martín-Vide, C., Păun, A.: On the universality of P systems with minimal symport/antiport rules. In: Jonoska, N., Păun, G., Rozenberg, G. (eds.) Aspects of Molecular Computing. LNCS, vol. 2950, pp. 254–265. Springer, Heidelberg (2003)
Margenstern, M., Rogozhin, V., Rogozhin, Y., Verlan, S.: About P systems with minimal symport/antiport rules and four membranes. In: [35], pp. 283–294
Martín-Vide, C., Păun, A., Păun, G.: On the power of P systems with symport rules. Journal of Universal Computer Science 8, 317–331 (2002)
Martín-Vide, C., Pazos, J., Păun, G., Rodrí, A.: A. Rodrí guez-Patón: Tissue P systems. Theoretical Computer Science 296, 295–326 (2003)
Mauri, G., Păun, G., Zandron, C. (eds.): Pre-Proceedings of Fifth Workshop on Membrane Computing (WMC5), Universitá di Milano-Bicocca, Italy, June 14–16 (2004)
Mauri, G., Păun, G., Pérez-Jiménez, M.J., Rozenberg, G., Salomaa, A. (eds.): WMC 2004. LNCS, vol. 3365. Springer, Heidelberg (2005)
Minsky, M.L.: Finite and infinite machines. Prentice Hall, Englewood Cliffs (1967)
Păun, A., Păun, G.: The power of communication: P systems with symport/antiport. New Generation Computing 20, 295–305 (2002)
Păun, G.: Computing with membranes. Journal of Computer and Systems Science 61, 108–143 (2000)
Păun, G.: Membrane computing. An Introduction. Springer, Heidelberg (2002)
Păun, G.: Further twenty six open problems in membrane computing. In: [25], pp. 249–262
Păun, G., Pazos, J., Perez-Jimenez, M.J., Rodriguez-Paton, A.: Symport/antiport P systems with three objects are universal. Fundamenta Informaticae 64, 1–4 (2005)
Păun, G., Riscos-Núñez, A., Romero-Jiménez, A., Sancho-Caparrini, F. (eds.): Second Brainstorming Week on Membrane Computing. Technical report of Research Group on Natural Computing, University of Seville, TR 01 (2004)
Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597. Springer, Heidelberg (2003)
Rozenberg, G., Salomaa, A. (eds.): Handbook of formal languages (3 volumes). Springer, Berlin (1997)
Vaszil, G.: On the size of P systems with minimal symport/antiport. In: [35], pp. 422–431
Verlan, S.: Optimal results on tissue P systems with minimal symport/antiport. Presented at EMCC meeting, Lorentz Center, Leiden, The Netherlands, 22–26 November (2004)
Verlan, S.: Tissue P systems with minimal symport/antiport. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 418–430. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alhazov, A., Freund, R., Rogozhin, Y. (2006). Computational Power of Symport/Antiport: History, Advances, and Open Problems. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2005. Lecture Notes in Computer Science, vol 3850. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11603047_1
Download citation
DOI: https://doi.org/10.1007/11603047_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30948-2
Online ISBN: 978-3-540-32340-2
eBook Packages: Computer ScienceComputer Science (R0)