Abstract
P systems are a model of hierarchically compartmentalized multiset rewriting. We introduce a novel kind of P systems in which rules are dynamically constructed in each step by non-deterministic pairing of left-hand and right-hand sides. We define three variants of right-hand side randomization and compare each of them with the power of conventional P systems. It turns out that all three variants enable non-cooperative P systems to generate exponential (and thus non-semi-linear) number languages. We also give a binary normal form for one of the variants of P systems with randomized rule right-hand sides.
A. Alhazov—The work is supported by National Natural Science Foundation of China (61320106005, 61033003, and 61772214) and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012).
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.: A note on P systems with activators. In: Păun, G., Riscos-Núñez, A., Romero-Jiménez, A., Sancho-Caparrini, F. (eds.) Second Brainstorming Week on Membrane Computing, Sevilla, Spain, 2–7 February 2004, pp. 16–19 (2004)
Alhazov, A., Freund, R., Ivanov, S.: P systems with randomized right-hand sides of rules. In: 15th Brainstorming Week on Membrane Computing, Sevilla, Spain, 31 January–5 February 2017 (2017)
Alhazov, A., Freund, R., Ivanov, S., Oswald, M.: Observations on P systems with states. In: Gheorghe, M., Petre, I., Pérez-Jiménez, M.J., Rozenberg, G., Salomaa, A. (eds.) Multidisciplinary Creativity. Hommage to Gheorghe Păun on His 65th Birthday, Spandugino (2015)
Alhazov, A., Ivanov, S., Rogozhin, Y.: Polymorphic P systems. In: Gheorghe, M., Hinze, T., Păun, G., Rozenberg, G., Salomaa, A. (eds.) CMC 2010. LNCS, vol. 6501, pp. 81–94. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-18123-8_9
Arroyo, F., Baranda, A.V., Castellanos, J., Păun, G.: Membrane computing: the power of (rule) creation. J. Univers. Comput. Sci. 8, 369–381 (2002)
Çapuni, I., Gács, P.: A turing machine resisting isolated bursts of faults. CoRR, abs/1203.1335 (2012)
Cavaliere, M., Genova, D.: P systems with symport/antiport of rules. In: Păun, G., Riscos-Núñez, A., Romero-Jiménez, A., Sancho-Caparrini, F. (eds.) Second Brainstorming Week on Membrane Computing, Sevilla, Spain, 2–7 February 2004, pp. 102–116 (2004)
Cavaliere, M., Ionescu, M., Ishdorj, T.-O.: Inhibiting/de-inhibiting rules in P systems. In: Mauri, G., Păun, G., Pérez-Jiménez, M.J., Rozenberg, G., Salomaa, A. (eds.) WMC 2004. LNCS, vol. 3365, pp. 224–238. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31837-8_13
Freund, R.: Generalized P-systems. In: Ciobanu, G., Păun, G. (eds.) FCT 1999. LNCS, vol. 1684, pp. 281–292. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48321-7_23
Freund, R.: P systems working in the sequential mode on arrays and strings. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 188–199. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30550-7_16
Freund, R., Leporati, A., Mauri, G., Porreca, A.E., Verlan, S., Zandron, C.: Flattening in (tissue) P systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds.) CMC 2013. LNCS, vol. 8340, pp. 173–188. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54239-8_13
Ivanov, S.: Polymorphic P systems with non-cooperative rules and no ingredients. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Sosík, P., Zandron, C. (eds.) CMC 2014. LNCS, vol. 8961, pp. 258–273. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-14370-5_16
Păun, G.: Computing with membranes. J. Comput. Syst. Sci. 61, 108–143 (1998)
Păun, G., Rozenberg, G., Salomaa, A.: The Oxford Handbook of Membrane Computing. Oxford University Press Inc., New York (2010)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 3. Springer, New York (1997). https://doi.org/10.1007/978-3-642-59126-6
Bulletin of the International Membrane Computing Society (IMCS). http://membranecomputing.net/IMCSBulletin/index.php
The P Systems Website. http://ppage.psystems.eu/
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Alhazov, A., Freund, R., Ivanov, S. (2018). Hierarchical P Systems with Randomized Right-Hand Sides of Rules. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Zandron, C. (eds) Membrane Computing. CMC 2017. Lecture Notes in Computer Science(), vol 10725. Springer, Cham. https://doi.org/10.1007/978-3-319-73359-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-73359-3_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-73358-6
Online ISBN: 978-3-319-73359-3
eBook Packages: Computer ScienceComputer Science (R0)