P systems with limited number of objects
Tóm tắt
P systems are a model of compartmentalized multiset rewriting inspired by the structure of living cells and the way they function. In this paper, we focus of a variant in P systems in which membranes have limited capacity, i.e., the number of objects they may hold is limited by a fixed bound. This feature corresponds to an important physical property of cellular compartments. We propose several possible semantics of limited capacity and show that one of them allows real-time simulations of partially blind register machines, while the other one allows for obtaining computational completeness.
Tài liệu tham khảo
Alhazov, A. (2006). P systems without multiplicities of symbol-objects. Information Processing Letters, 100(3), 124–129.
Alhazov, A., & Freund, R. (2014). P systems with toxic objects. In Gheorghe, M., Rozenberg, G., Salomaa, A., Sosík, P., & Zandron C. (Eds.), Membrane Computing – 15th International Conference, CMC 2014, Prague, Czech Republic, August 20–22, 2014, Revised Selected Papers, volume 8961 of Lecture Notes in Computer Science, pages 99–125. Springer.
Alhazov, A., & Freund, R. (2014). Length P systems. Fundamenta Informaticae, 134(1–2), 17–37.
Alhazov, A., Freund, R., & Ivanov, S. (2020). P systems with limited capacity. In David Orellana-Martín, Gheorghe Păun, Agustín Riscos-Núñez, and Ignacio Pérez-Hurtado, editors, Proceedings 18th Brainstorming Week on Membrane Computing, Sevilla, February 4–7, 2020, pages 33–47. RGNC REPORT 1/2020, Research Group on Natural Computing, Universidad de Sevilla.
Alhazov, A., Freund, R., & Ivanov, S. (2020). P systems with limiting the number of objects in membranes. In Rudolf Freund and Tseren-Onolt Ishdorj, editors, Electronic Proceedings of the International Conference on Membrane Computing 2020 (ICMC 2020), Wien, September 14–17, 2020, pp. 83–98. TU Wien.
Alhazov, A., Freund, R., & Riscos-Núñez, A. (2006). Membrane division, restricted membrane creation and object complexity in P systems. International Journal of Computer Mathematics, 83(7), 529–547.
Dassow, J., & Păun, Gh. (1989). Regulated Rewriting in Formal Language Theory. Berlin: Springer.
Freund, R., Kari, L., Oswald, M., & Sosík, P. (2005). Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 330(2), 251–266.
Freund, R., & Sosík, P. (2015). On the power of catalytic P systems with one catalyst. In Grzegorz Rozenberg, Arto Salomaa, José M. Sempere, and Claudio Zandron, editors, Membrane Computing – 16th International Conference, CMC 2015, Valencia, Spain, August 17–21, 2015, Revised Selected Papers, volume 9504 of Lecture Notes in Computer Science, pages 137–152. Springer.
Marvin, L. (1967). Computation. Finite and Infinite Machines. Englewood Cliffs: Prentice Hall.
Păun, Gh. (2000). Computing with membranes. Journal of Computer and System Sciences, 61(1), 108–143.
Păun, Gh. (2002). Membrane Computing: An Introduction. Berlin: Springer.
Păun, Gh., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford Handbook of Membrane Computing. Oxford: Oxford University Press.
Rozenberg, G., & Salomaa, A. (Eds.). (1997). Handbook of Formal Languages. Berlin: Springer.
The P Systems Website. (2019). http://ppage.psystems.eu/.