×

Monodirectional tissue P systems with channel states. (English) Zbl 1475.68124

Summary: Tissue P systems with channel states are non-deterministic bio-inspired computing devices that evolve by the interchange of objects among regions, determined by the existence of some special objects on channels called states. However, in cellular biology, the movement of molecules across a membrane is transported from high to low concentration, inspired by this biological fact, in this paper, a variant of P systems, named monodirectional tissue P systems with channel states, where communication happens between two given regions only in one direction, is considered. We show that monodirectional tissue P systems using two cells are universal if a maximal length 1 for each symport rule and any number of states or a maximal length 2 for each symport rule and 4 states are combined. Universality result is also achieved by monodirectional tissue P systems with 5 states, any number of cells and a maximal length 1 for each symport rule. Besides, computational efficiency of monodirectional tissue P systems is analyzed when cell division rules are incorporated, and a solution to the Boolean satisfiability problem (the SAT problem) is provided by such systems using a maximal length 2 for each symport rule.

MSC:

68Q07 Biologically inspired models of computation (DNA computing, membrane computing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alhazov, A.; Freund, R.; Leporati, A.; Oswald, M.; Zandron, C., (Tissue) P systems with unit rules and energy assigned to membranes, Fundam. Inform., 74, 4, 391-408 (2006) · Zbl 1106.68038
[2] Alhazov, A.; Freund, R.; Oswald, M., Tissue P systems with antiport rules and small numbers of symbols and cells, Lect. Notes Comput. Sci., 3572, 100-111 (2005) · Zbl 1132.68386
[3] Alhazov, A.; Freund, R., Variants of small universal P systems with catalysts, Fundam. Inform., 138, 1-2, 227-250 (2015) · Zbl 1357.68055
[4] Alhazov, A.; Pan, L., Polarizationless P systems with active membranes, Grammars, 7, 141-159 (2004)
[5] Bel-Enguix, G.; Gramatovici, R., Parsing with active P automata, Lect. Notes Comput. Sci., 2933, 31-42 (2003) · Zbl 1202.68181
[6] Csuhaj-Varjú, E.; Margenstern, M.; Vaszil, G.; Verlan, S., On small universal antiport P systems, Theor. Comput. Sci., 372, 2, 152-164 (2007) · Zbl 1111.68038
[7] Díaz-Pernil, D.; Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., A uniform family of tissue P system with cell division solving 3-COL in a linear time, Theor. Comput. Sci., 404, 1-2, 76-87 (2008) · Zbl 1151.68016
[8] Enguix, G. B., Unstable P systems: applications to linguistics, Lect. Notes Comput. Sci., 3365, 190-209 (2005) · Zbl 1117.68353
[9] Freund, R.; Oswald, M.; Schirk, T., How a membrane agent buys goods in a membrane store, Prog. Nat. Sci., 17, 4, 442-448 (2007) · Zbl 1160.68381
[10] Freund, R.; Păun, A., P systems with active membranes and without polarizations, Soft Comput., 9, 9, 657-663 (2005) · Zbl 1101.68577
[11] Freund, R.; Păun, G.; Pérez-Jiménez, M. J., Tissue P systems with channel states, Theor. Comput. Sci., 330, 1, 101-116 (2005) · Zbl 1078.68061
[12] Frisco, P.; Govan, G.; Leporati, A., Asynchronous P systems with active membranes, Theor. Comput. Sci., 429, 74-86 (2012) · Zbl 1277.68076
[13] Garey, M. R.; Johnson, D. J., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[14] Ionescu, M.; Păun, G.; Yokomori, T., Spiking neural P systems, Fund. Inform., 71, 2-3, 279-308 (2006) · Zbl 1110.68043
[15] Jiang, S.; Wang, Y.; Su, Y., A uniform solution to SAT problem by symport/antiport P systems with channel states and membrane division, Soft Comput., 23, 3903-3911 (2019) · Zbl 1418.68090
[16] Jiang, S.; Wang, Y.; Xu, F.; Deng, J., Communication P systems with channel statesworking in flat maximally parallel manner, Fund. Inform., 168, 1, 1-24 (2019) · Zbl 1423.68171
[17] Leporati, A.; Manzoni, L.; Mauri, G.; Porreca, A. E.; Zandron, C., Membrane division, oracles, and the counting hierarchy, Fund. Inform., 138, 1-2, 97-111 (2015) · Zbl 1357.68064
[18] Leporati, A.; Manzoni, L.; Mauri, G.; Porreca, A. E.; Zandron, C., Monodirectional P systems, Nat. Comput., 15, 4, 551-564 (2016) · Zbl 1415.68092
[19] Macías-Ramos, L. F.; Song, B.; Valencia-Cabrera, L.; Pan, L.; Pérez-Jiménez, M. J., Membrane fission: a computational complexity perspective, Complexity, 21, 6, 321-334 (2016)
[20] Manca, V.; Bianco, L., Biological networks in metabolic P systems, BioSystems, 91, 3, 489-498 (2008)
[21] Martin-Vide, C.; Pazos, J.; Păun, G.; Rodriguez-Patón, A., Tissue P systems, Theor. Comput. Sci., 296, 2, 295-326 (2003) · Zbl 1045.68063
[22] Minsky, M. L., Computation: Finite and Infinite Machines (1967), Prentice-Hall Inc: Prentice-Hall Inc Englewood Cliffs, N.J. · Zbl 0195.02402
[23] Pan, L.; Păun, G.; Song, B., Flat maximal parallelism in P systems with promoters, Theor. Comput. Sci., 623, 83-91 (2016) · Zbl 1336.68073
[24] Pan, L.; Pérez-Jiménez, M. J., Computational complexity of tissue-like P systems, J. Complexity, 26, 3, 296-315 (2010) · Zbl 1195.68050
[25] Păun, A.; Păun, G., The power of communication: P systems with symport/antiport, New Generat. Comput., 20, 3, 295-306 (2002) · Zbl 1024.68037
[26] Păun, A.; Păun, G.; Rozenberg, G., Computing by communication in networks of membranes, Int. J. Found. Comput. Sci., 13, 6, 779-798 (2002) · Zbl 1067.68072
[27] Păun, G., Computing with membranes, J. Comput. Syst. Sci., 61, 1, 108-143 (2000) · Zbl 0956.68055
[28] Păun, G., Computing with Membranes: An Introduction (2002), Springer-Verlag: Springer-Verlag Berlin
[29] Păun, G.; Păun, R., Membrane computing and economics: numerical P systems, Fund. Inform., 73, 1-2, 213-227 (2006) · Zbl 1157.68373
[30] Păun, G.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., Tissue P systems with cell division, Int. J. Comput. Commun. Control, 3, 3, 295-303 (2008)
[31] (Păun, G.; Rozenberg, G.; Salomaa, A., The Oxford Handbook of Membrane Computing (2010), Oxford University Press: Oxford University Press New York) · Zbl 1237.68001
[32] Peng, H.; Li, B.; Wang, J.; Song, X.; Wang, T.; Valencia-Cabrera, L.; Pérez-Hurtado, I.; Riscos-Núñez, A.; Pérez-Jiménez, M. J., Spiking neural P systems with inhibitory rules, Knowl.-Based Syst., 188, Article 105064 pp. (2020)
[33] Peng, H.; Wang, J., Coupled neural P systems, IEEE Trans. Neural Networks Learn., 30, 6, 1672-1682 (2019)
[34] Peng, H.; Wang, J.; Pérez-Jiménez, M. J.; Riscos-Núñez, A., Dynamic threshold neural P systems, Knowl.-Based Syst., 163, 875-884 (2019)
[35] Pérez-Jiménez, M. J.; Riscos-Núñez, A., Solving the Subset-Sum problem by active membranes, New Generat. Comput., 23, 4, 339-356 (2005) · Zbl 1092.68043
[36] Pérez-Jiménez, M. J.; Romero-Jiménez, A.; Sancho-Caparrini, F., The P versus NP problem through cellular computing with membranes, Lect. Notes Comput. Sci., 2950, 338-352 (2004) · Zbl 1200.68117
[37] Romero-Campero, F. J.; Pérez-Jiménez, M. J., Modelling gene expression control using P systems: the lac operon, a case study, BioSystems, 91, 3, 438-457 (2008)
[38] (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 3 (1997), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0866.68057
[39] Song, B.; Kong, Y., Solution to PSPACE-complete problem using P systems with active membranes with time-freeness, Math. Probl. Eng., 5793234 (2019) · Zbl 1435.68098
[40] Song, B.; Li, K.; Orellana-Martín, D.; Valencia-Cabrera, L.; Pérez-Jiménez, M. J., Cell-like P systems with evolutional symport/antiport rules and membrane creation, Inform. Comput. (2020) · Zbl 1496.68144
[41] Song, T.; Pan, L., Spiking neural P systems with rules on synapses working in maximum spiking strategy, IEEE Trans. Nanobiosci., 14, 4, 465-477 (2015)
[42] Song, B.; Pan, L.; Pérez-Jiménez, M. J., Cell-like P systems with channel states and symport/antiport rules, IEEE Trans. Nanobiosci., 15, 6, 555-566 (2016)
[43] Song, B.; Pérez-Jiménez, M. J.; Păun, G.; Pan, L., Tissue P systems with channel states working in the flat maximally parallel way, IEEE Trans. Nanobiosci., 15, 7, 645-656 (2016)
[44] Song, B.; Song, T.; Pan, L., A time-free uniform solution to subset sum problem by tissue P systems with cell division, Math. Struct. Comput. Sci., 27, 1, 17-32 (2017) · Zbl 1364.68207
[45] Song, B.; Zeng, X.; Jiang, M.; Pérez-Jiménez, M. J., Monodirectional tissue P systems with promoters, IEEE Trans. Cybern. (2020)
[46] Song, B.; Zhang, C.; Pan, L., Tissue-like P systems with evolutional symport/antiport rules, Inf. Sci., 378, 177-193 (2017) · Zbl 1429.68074
[47] Wu, T.; Bıˇlbıˇe, F. D.; Păun, A.; Pan, L.; Neri, F., Simplified and yet turing universal spiking neural P systems with communication on request, Int. J. Neural Syst., 28, 8, 1850013 (2018)
[48] Wu, T.; Păun, A.; Zhang, Z.; Pan, L., Spiking neural P systems with polarizations, IEEE Trans. Neural Networks Learn., 29, 8, 3349-3360 (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.