×

Time-free cell-like P systems with multiple promoters/inhibitors. (English) Zbl 1460.68040

Summary: Cell-like P systems with promoters/inhibitors (PIC-P systems) are a class of distributed and parallel computing models inspired by the function of regulating biochemical reactions by enzymes in biological cells. In PIC-P systems, each evolution rule (rule for short) can be associated with one promoter/inhibitor which helps control the evolution process of objects. In this work, we propose a novel variant of PIC-P systems, called time-free cell-like P systems with multi-promoters/inhibitors (time-free MPIC-P systems for short). In such systems, each rule can be associated with multiple promoters/inhibitors, and the execution time of each rule is extended from one time unit to a random number of time units. These two characters make the time-free MPIC-P systems closer to biological cells. We also investigate the computational power of time-free MPIC-P systems. As results, it is achieved by simulating the matrix grammar that such systems can generate the set of lengths of recursively enumerable languages, that is, Turing universality can be achieved. This indicates that the time-free working mode will not reduce the computational power of PIC-P systems, by using multiple promoters/inhibitors.

MSC:

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

References:

[1] Păun, G.; Rozenberg, G.; Salomaa, A., The Oxford Handbook of Membrane Computing (2010), Oxford University Press, Inc. · Zbl 1237.68001
[2] 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, Inf. Comput., Article 104542 pp. (2020) · Zbl 1496.68144
[3] Song, B.; Zhang, C.; Pan, L., Tissue-like P systems with evolutional symport/antiport rules, Inf. Sci., 378, 177-193 (2017) · Zbl 1429.68074
[4] Pan, L.; Song, B., P systems with rule production and removal, Fundam. Inform., 171, 1-4, 313-329 (2020) · Zbl 1435.68097
[5] Song, T.; Rodríguez-Patón, A.; Zheng, P.; Zeng, X., Spiking neural P systems with colored spikes, IEEE Trans. Cogn. Dev. Syst., 10, 4, 1106-1115 (2018)
[6] Song, T.; Gong, F.; Liu, X.; Zhao, Y.; Zhang, X., Spiking neural P systems with white hole neurons, IEEE Trans. Nanobiosci., 15, 7, 666-673 (2016)
[7] Zeng, X.; Zhang, X.; Song, T.; Pan, L., Spiking neural P systems with thresholds, Neural Comput., 26, 7, 1340-1361 (2014) · Zbl 1415.68104
[8] Cabarle, F. G.C.; de la Cruz, R. T.A.; Cailipan, D. P.P.; Zhang, D.; Liu, X.; Zeng, X., On solutions and representations of spiking neural P systems with rules on synapses, Inf. Sci., 501, 30-49 (2019) · Zbl 1453.68077
[9] 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. (2019)
[10] Song, B.; Zeng, X.; Jiang, M.; Perez-Jimenez, M. J., Monodirectional tissue P systems with promoters, IEEE Trans. Cybern. (2020)
[11] Zhang, X.; Pan, L.; Păun, A., On the universality of axon P systems, IEEE Trans. Neural Netw. Learn. Syst., 26, 11, 2816-2829 (2015)
[12] Song, T.; Zheng, P.; Wong, M. D.; Jiang, M.; Zeng, X., On the computational power of asynchronous axon membrane systems, IEEE Trans. Emerg. Top. Comput. Intell., 1-9 (2019)
[13] Song, X.; Peng, H.; Wang, J.; Ning, G.; Sun, Z., Small universal asynchronous spiking neural P systems with multiple channels, Neurocomputing, 378, 1-8 (2020)
[14] Zeng, X.; Xu, L.; Liu, X.; Pan, L., On languages generated by spiking neural P systems with weights, Inf. Sci., 278, 423-433 (2014) · Zbl 1354.68083
[15] Zhang, X.; Liu, Y.; Luo, B.; Pan, L., Computational power of tissue P systems for generating control languages, Inf. Sci., 278, 285-297 (2014) · Zbl 1354.68084
[16] Orellana-Martín, D.; Valencia-Cabrera, L.; Riscos-Núñez, A.; Pérez-Jiménez, M. J., A path to computational efficiency through membrane computing, Theor. Comput. Sci., 777, 443-453 (2019) · Zbl 1423.68176
[17] Luo, Y.; Xiong, Z.; Zhang, G., Time-free solution to SAT problem by tissue P systems, Math. Probl. Eng. (2017) · Zbl 1426.68255
[18] Guo, P.; Ji, J.; Chen, H.; Liu, R., Solving all-SAT problems by P systems, Chin. J. Electron., 24, 4, 744-749 (2015)
[19] Song, B.; Kong, Y., Solution to PSPACE-complete problem using P systems with active membranes with time-freeness, Math. Probl. Eng. (2019) · Zbl 1435.68098
[20] Zhang, X.; Li, J.; Zhang, L., A multi-objective membrane algorithm guided by the skin membrane, Nat. Comput., 15, 4, 597-610 (2016) · Zbl 1415.68211
[21] Ju, Y.; Zhang, S.; Ding, N.; Zeng, X.; Zhang, X., Complex network clustering by a multi-objective evolutionary algorithm based on decomposition and membrane structure, Sci. Rep., 6, Article 33870 pp. (2016)
[22] Wang, J.; Peng, H.; Yu, W.; Ming, J.; Pérez-Jiménez, M. J.; Tao, C.; Huang, X., Interval-valued fuzzy spiking neural P systems for fault diagnosis of power transmission networks, Eng. Appl. Artif. Intell., 82, 102-109 (2019)
[23] Song, T.; Zeng, X.; Zheng, P.; Jiang, M.; Rodríguez-Patón, A., A parallel workflow pattern modeling using spiking neural P systems with colored spikes, IEEE Trans. Nanobiosci., 17, 4, 474-484 (2018)
[24] Baumgardner, J.; Acker, K.; Adefuye, O.; Crowley, S. T.; DeLoache, W.; Dickson, J. O.; Heard, L.; Martens, A. T.; Morton, N.; Ritter, M., Solving a Hamiltonian path problem with a bacterial computer, J. Biol. Eng., 3, 11 (2009)
[25] Sakakibara, Y.; Nakagawa, H.; Nakashima, Y.; Yugi, K., Implementing in vivo cellular automata using toggle switch and inter-bacteria communication mechanism, (2007 2nd Bio-Inspired Models of Network, Information and Computing Systems (2007), IEEE), 322-325
[26] Weiss, R.; Basu, S.; Hooshangi, S.; Kalmbach, A.; Karig, D.; Mehreja, R.; Netravali, I., Genetic circuit building blocks for cellular computation, communications, and signal processing, Nat. Comput., 2, 1, 47-84 (2003)
[27] Bottoni, P.; Martín-Vide, C.; Păun, G.; Rozenberg, G., Membrane systems with promoters/inhibitors, Acta Inform., 38, 10, 695-720 (2002) · Zbl 1034.68038
[28] Song, T.; Macías-Ramos, L. F.; Pan, L.; Pérez-Jiménez, M. J., Time-free solution to SAT problem using P systems with active membranes, Theor. Comput. Sci., 529, 61-68 (2014) · Zbl 1358.68103
[29] Pan, L.; Zeng, X.; Zhang, X., Time-free spiking neural P systems, Neural Comput., 23, 5, 1320-1342 (2011) · Zbl 1216.68113
[30] 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
[31] Dassow, J.; Păun, G., Regulated Rewriting in Formal Language Theory (2012), Springer Publishing Company, Incorporated
[32] Freund, R.; Păun, G., On the number of non-terminal symbols in graph-controlled, programmed and matrix grammars, (International Conference on Machines, Computations, and Universality. International Conference on Machines, Computations, and Universality, Lecture Notes in Computer Science, vol. 2055 (2001), Springer), 214-225 · Zbl 0984.68091
[33] Cavaliere, M.; Sburlan, D., Time-independent P systems, (International Workshop on Membrane Computing. International Workshop on Membrane Computing, Lecture Notes in Computer Science, vol. 3365 (2004), Springer), 239-258 · Zbl 1117.68355
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.