When catalytic P systems with one catalyst can be computationally complete
Tóm tắt
Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particular the problem of using only one catalyst in the whole system: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining computational completeness even with only one catalyst. In this paper, we show that one catalyst is sufficient for obtaining computational completeness if either catalytic rules have weak priority over non-catalytic rules or else instead of the standard maximally parallel derivation mode, we use the derivation mode maxobjects, i.e., we only take those multisets of rules which affect the maximal number of objects in the underlying configuration.
Tài liệu tham khảo
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, Lecture Notes in Computer Science, vol. 8961, pp. 99–125. Springer. https://doi.org/10.1007/978-3-319-14370-5_7.
Alhazov, A., Freund, R., & Ivanov, S. (2020). Catalytic P systems with weak priority of catalytic rules. In: Freund, R. (Ed.) Proceedings ICMC 2020, September 14–18, 2020, TU Wien, pp. 67–82.
Alhazov, A., Freund, R., & Ivanov, S. (2020). Computational completeness of catalytic P systems with weak priority of catalytic rules over non-cooperative rules. In: Orellana-Martín, D., Păun, Gh., Riscos-Núñez, A., Pérez-Hurtado, I. (Eds.) Proceedings 18th Brainstorming Week on Membrane Computing, Sevilla, February 4–7, 2020. RGNC REPORT 1/2020, Research Group on Natural Computing, Universidad de Sevilla, pp. 21–32.
Dassow, J., & Păun, Gh. (1989). Regulated Rewriting in Formal Language Theory. Springer. https://www.springer.com/de/book/9783642749346.
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. https://doi.org/10.1016/j.tcs.2004.06.029.
Freund, R., Leporati, A., Mauri, G., Porreca, A. E., Verlan, S., & Zandron, C. (2014). Flattening in (tissue) P systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Yu., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, Lecture Notes in Computer Science, vol. 8340, pp. 173–188. Springer. https://doi.org/10.1007/978-3-642-54239-8_13.
Freund, R., Oswald, M., & Păun, Gh. (2015). Catalytic and purely catalytic P systems and P automata: Control mechanisms for obtaining computational completeness. Fundamenta Informaticae, 136(1–2), 59–84. https://doi.org/10.3233/FI-2015-1144.
Freund, R., & Sosík, P. (2015). On the power of catalytic P systems with one catalyst. In: Rozenberg, G., Salomaa, A., Sempere, J. M., Zandron, C. (eds.) Membrane Computing—16th International Conference, CMC 2015, Valencia, Spain, August 17–21, 2015, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9504, pp. 137–152. Springer. https://doi.org/10.1007/978-3-319-28475-0_10.
Minsky, M. L. (1967). Computation: Finite and infinite machines. Englewood Cliffs, NJ: Prentice Hall.
Păun, Gh. (2000). Computing with membranes. Journal of Computer and System Sciences, 61(1), 108–143. https://doi.org/10.1006/jcss.1999.1693.
Păun, Gh. (2002). Membrane Computing: An introduction. Springer. https://doi.org/10.1007/978-3-642-56196-2.
Păun, Gh., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford Handbook of Membrane Computing. Oxford University Press.
Rozenberg, G., & Salomaa, A. (Eds.) (1997). Handbook of Formal Languages. Springer. https://doi.org/10.1007/978-3-642-59136-5.
The P Systems Website. http://ppage.psystems.eu/.