Abstract
Labelled splicing P systems are distributed parallel computing models, where sets of strings that evolve by splicing rules are labelled. In this work, we consider labelled splicing systems with the following modifications: (i) The strings in the membranes are present in arbitrary number of copies; (ii) the rules in the regions are finite in number. Results on the language family generated by the labelled splicing system in comparison with the language families of the Chomsky hierarchy, including recursively enumerable languages, are obtained, by involving only either one or two membranes in the P systems considered.
K.G. Subramanian—Honorary visiting professor at Liverpool Hope University.
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
Similar content being viewed by others
References
Alhazov, A., Rogozhin, Y., Verlan, S.: On small universal splicing systems. Int. J. Found. Comput. Sci. 23(7), 1423–1438 (2012)
Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory. Springer, Heidelberg (1989)
Freund, F., Freund, R., Oswald, M.: Splicing test tube systems and their relation to splicing membrane systems. In: Jonoska, N., Păun, G., Rozenberg, G. (eds.) Aspects of Molecular Computing. LNCS, vol. 2950, pp. 139–151. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24635-0_10
Freund, R., Kari, L., Păun, G.: DNA computing based on splicing: the existence of universal computers. Theor. Comput. Syst. 32, 69–112 (1999)
Head, T.: Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviours. B. Math. Biol. 49, 737–759 (1987)
Head, T., Păun, G., Pixton, D.: Language theory and molecular genetics: generative mechanisms suggested by DNA recombination. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2, pp. 295–360. Springer, Heidelberg (1996). https://doi.org/10.1007/978-3-662-07675-0_7
Krithivasan, K., Păun, G., Ramanujan, A.: On controlled P systems. Fundam. Inf. 131(3–4), 451–464 (2014)
Mahalingam, K., Paul, P., Rama, R.: Chomsky control on splicing P system. In: Proceedings of the 4th Asian Conference on Membrane Computing, Hefei, China (2015)
Mitrana, V., Petre, I., Rogojin, V.: Accepting splicing systems. Theor. Comput. Sci. 411, 2414–2422 (2010)
Pan, L., Păun, G., Zhang, G., Neri, F.: Spiking neural P systems with communication on request. Int. J. Neural Syst. https://doi.org/10.1142/S0129065717500423
Păun, G.: Computing with membranes. J. Comput. Syst. Sci. 61(1), 108–143 (2000)
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Heidelberg (1998)
Păun, G., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, New York (2010)
Ramanujan, A., Krithivasan, K.: Control words of transition P systems. In: Bansal, J.C., Singh, P.K., Deep, K., Pant, M., Nagar, A.K. (eds.) BIC-TA 2012. AISC, vol. 201, pp. 145–155. Springer, Heidelberg (2013). https://doi.org/10.1007/978-81-322-1038-2_13
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages (3 Volumes). Springer, Heidelberg (1997)
Verlan, S., Margenstern, M.: About splicing P systems with one membrane. Fundam. Inf. 65(3), 279–290 (2005)
Wu, T., Zhang, Z., Păun, G., Pan, L.: Cell-like spiking neural P systems. Theor. Comput. Sci. 623, 180–189 (2016)
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)
Song, T., Pan, L.: Spiking neural P systems with rules on synapses working in maximum spikes consumption strategy. IEEE Trans. NanoBiosci. 14(1), 37–43 (2015)
Zhang, X., Liu, Y., Luo, B., Pan, L.: Computational power of tissue P systems for generating control languages. Inf. Sci. 278, 285–297 (2014)
Zhang, X., Pan, L., Păun, A.: On universality of axon P systems. IEEE Trans. Neural. Netw. Learn. 26(11), 2816–2829 (2015)
Acknowledgments
The authors are grateful to the reviewers for their very useful comments which helped to improve the presentation. The second author acknowledges University Grants Commission for the financial support. The work was supported by National Natural Science Foundation of China (61320106005, 61602192, and 61772214), China Postdoctoral Science Foundation (2016M600592, 2017T100554), and the Innovating Scientists and Technicians Troop Construction Projects of Henan Province (154200510012).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Mahalingam, K., Paul, P., Song, B., Pan, L., Subramanian, K.G. (2017). Derivation Languages of Splicing P Systems. In: He, C., Mo, H., Pan, L., Zhao, Y. (eds) Bio-inspired Computing: Theories and Applications. BIC-TA 2017. Communications in Computer and Information Science, vol 791. Springer, Singapore. https://doi.org/10.1007/978-981-10-7179-9_38
Download citation
DOI: https://doi.org/10.1007/978-981-10-7179-9_38
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-7178-2
Online ISBN: 978-981-10-7179-9
eBook Packages: Computer ScienceComputer Science (R0)