Small Universal Tissue P Systems with Symport/Antiport Rules

  • Xingyi Zhang Key Lab of Intelligent Computing and Signal Processing of Ministry of Education School of Computer Science and Technology Anhui University, Hefei 230039, China
  • Bin Luo Key Lab of Intelligent Computing and Signal Processing of Ministry of Education School of Computer Science and Technology Anhui University, Hefei 230039, China
  • Linqiang Pan Key Laboratory of Image Processing and Intelligent Control Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, China

Abstract

In this note, we consider the problem of looking for small universal one-symbol tissue P systems with symport/antiport rules. It is proved that six cells suffice to generate any recursively enumerable set of natural numbers by such a onesymbol tissue P system with symport/antiport rules, under the restriction that only one channel is allowed between two cells or between a cell and the environment. As for the case of allowing two channels between a cell and the environment, it is shown that the computational completeness can be obtained by one-symbol tissue P systems with symport/antiport rules having at most five cells. These results partially answer an open problem formulated by Artiom Alhazov, Rudolf Freund and Marion Oswald.

References

[1] A. Alhazov, R. Freund, M. Oswald, Tissue P Systems with Symport/Antiport Rules and mall Numbers of Symbols and Cells, Lecture Notes in Computer Science, 3572:100–111, 005.

[2] R. Freund, Gh. Păun, M.J. Pérez-Jiménez, Tissue-Like P Systems with Channel States, Theoretical Computer Science, 296:295–326, 2003.

[3] R. Freund, M. Oswald, Tissue P Systems with Symport/Antiport Rules of One Symbol are Computational Complete, in: M.A. Gutiérrez-Naranjo, Gh. Păun, M.J. Pérez-Jiménez (eds.), Proceedings of the European Science Foundation PESC Exploratory Workshop Cellular Computing (Complexity Aspects), Sevilla, pp.178–187, 2005.

[4] S.N. Krishna, K. Lakshmanan, R. Rama, Tissue P Systems with Contextual and Rewriting Rules, Lecture Notes in Computer Science, 2597:339–351, 2003.
http://dx.doi.org/10.1007/3-540-36490-0_22

[5] M. Minsky (eds.), Computation: Finite and Infinite Machines, Prentice Hall, 1967.

[6] C. Martín Vide, J. Pazos, Gh. Păun, A. Rodríguez Patón, Tissue P Systems, Theoretical Computer Science, 296:295–326, 2003.
http://dx.doi.org/10.1016/S0304-3975(02)00659-X

[7] Gh. Păun, Computing with Membranes, Journal of Computer and System Sciences, 1(1):108–143, 2000. ] A. Păun, Gh. Păun, The Power of Communication: P Systems with Symport/Antiport, New Generation Computing, 20(3):295–305, 2002.

[9] Gh. Păun, G. Rozenberg, A. Salomaa (eds.), Handbook of Membrane Computing, Oxford University Press, 2010.

[10] Y. Rogozhin, S. Verlan, On the Rule Complexity of Universal Tissue P Systems, Lecture Notes in Computer Science, 3850:356–362, 2006.
http://dx.doi.org/10.1007/11603047_24

[11] The P systems web page: http://ppage.psystems.eu
Published
2012-03-01
How to Cite
ZHANG, Xingyi; LUO, Bin; PAN, Linqiang. Small Universal Tissue P Systems with Symport/Antiport Rules. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 7, n. 1, p. 173-183, mar. 2012. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/1432>. Date accessed: 10 july 2020. doi: https://doi.org/10.15837/ijccc.2012.1.1432.

Keywords

membrane computing, tissue P system, symport/antiport rule, universality