Variants of derivation modes for which catalytic P systems with one catalyst are computationally complete

Journal of Membrane Computing - Tập 3 Số 4 - Trang 233-245 - 2021
Artiom Alhazov1, Rudolf Freund2, Sergiu Ivanov3, Sergey Verlan4
1Vladimir Andrunachievici Institute of Mathematics and Computer Science, Academiei 5, Chişinău, MD, 2028, Moldova
2Faculty of Informatics, TU Wien, Favoritenstraße 9–11, 1040, Wien, Austria
3IBISC, Université Évry, Paris-Saclay, 23, boulevard de France, 91034, Évry, France
4Univ. Paris Est Creteil, LACL, 94010, Creteil, France

Tóm tắt

Abstract

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: 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 even computational completeness with only one catalyst. Last year we could show that the derivation mode $$max_{objects}$$ m a x objects , where we only take those multisets of rules which affect the maximal number of objects in the underlying configuration one catalyst is sufficient for obtaining computational completeness without any other ingredients. In this paper we follow this way of research and show that one catalyst is also sufficient for obtaining computational completeness when using specific variants of derivation modes based on non-extendable multisets of rules: we only take those non-extendable multisets whose application yields the maximal number of generated objects or else those non-extendable multisets whose application yields the maximal difference in the number of objects between the newly generated configuration and the current configuration. A similar computational completeness result can even be obtained when omitting the condition of non-extendability of the applied multisets when taking the maximal difference of objects or the maximal number of generated objects. Moreover, we reconsider simple P system with energy control—both symbol and rule energy-controlled P systems equipped with these new variants of derivation modes yield computational completeness.

Từ khóa


Tài liệu tham khảo

Alhazov, A., Aman, B., Freund, R. (2014). P systems with anti-matter. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sosík, C. Zandron (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. 66–85. Springer https://doi.org/10.1007/978-3-319-14370-5_5

Alhazov, A., Aman, B., Freund, R., Păun, Gh. (2014). Matter and anti-matter in membrane systems. In: H. Jürgensen, J. Karhumäki, A. Okhotin (eds.) Descriptional complexity of formal systems – 16th International Workshop, DCFS 2014, Turku, Finland, August 5–8, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8614, pp. 65–76. Springer https://doi.org/10.1007/978-3-319-09704-6_7

Alhazov, A., Freund, R. (2014). P systems with toxic objects. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sosík, C. Zandron (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. (2016). Variants of energy-controlled P systems. In: Proceedings of NIT 2016

Alhazov, A., Freund, R., & Ivanov, S. (2019). Variants of P systems with activation and blocking of rules. Nat. Comput., 18(3), 593–608. https://doi.org/10.1007/s11047-019-09747-5

Alhazov, A., Freund, R., Ivanov, S. (2020). Catalytic P systems with weak priority of catalytic rules. In: R. Freund (ed.) Proceedings ICMC 2020, September 14–18, 2020, pp. 67–82. TU Wien

Alhazov, A., Freund, R., Ivanov, S. (2020). P systems with limiting the number of objects in membranes. In: R. Freund (ed.) Proceedings ICMC 2020, September 14–18, 2020, pp. 83–98. TU Wien

Alhazov, A., Freund, R., & Ivanov, S. (2021). P systems with limited number of objects. Journal of Membrane Computing, 3, 1–9. https://doi.org/10.1007/s41965-020-00068-6

Alhazov, A., Freund, R., & Ivanov, S. (2021). When catalytic P systems with one catalyst can be computationally complete. Journal of Membrane Computing. https://doi.org/10.1007/s41965-021-00079-x

Alhazov, A., Freund, R., Ivanov, S., Verlan, S. (2017). (Tissue) P systems with vesicles of multisets. In: E. Csuhaj-Varjú, P. Dömösi, Gy. Vaszil (eds.) Proceedings 15th International Conference on Automata and Formal Languages, AFL 2017, Debrecen, Hungary, September 4–6, 2017, EPTCS, vol. 252, pp. 11–25. https://doi.org/10.4204/EPTCS.252.6

Alhazov, A., Freund, R., Leporati, A., Oswald, M., & Zandron, C. (2006). (Tissue) P systems with unit rules and energy assigned to membranes. Fundam. Informaticae, 74(4), 391–408.

Alhazov, A., Freund, R., Oswald, M., & Verlan, S. (2009). Partial halting and minimal parallelism based on arbitrary rule partitions. Fundam. Inform., 91(1), 17–34. https://doi.org/10.3233/FI-2009-0031

Alhazov, A., Freund, R., & Sosík, P. (2015). Small P systems with catalysts or anti-matter simulating generalized register machines and generalized counter automata. Comput. Sci. J. Moldova, 23(3), 304–328.

Alhazov, A., Freund, R., & Verlan, S. (2017). P systems working in maximal variants of the set derivation mode. In: A. Leporati, G. Rozenberg, A. Salomaa, C. Zandron (eds.) Membrane Computing – 17th International Conference, CMC 2016, Milan, Italy, July 25–29, 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol. 10105, pp. 83–102. Springer https://doi.org/10.1007/978-3-319-54072-6_6

Ciobanu, G., Marcus, S., & Păun, Gh. (2009). New strategies of using the rules of a P system in a maximal way. power and complexity. Romanian Journal of Information Science and Technology 12(2), 21–37

Dassow, J., & Păun, Gh. (1989). Regulated Rewriting in Formal Language Theory. Springer

Freund, R. (2003). Energy-controlled P systems. In: Gh. Păun, G. Rozenberg, A. Salomaa, C. Zandron (eds.) Membrane Computing, pp. 247–260. Springer

Freund, R. (2013). Purely catalytic P systems: two catalysts can be sufficient for computational completeness. In A. Alhazov, S. Cojocaru, M. Gheorghe, Yu. Rogozhin (Eds.), CMC14 Proceedings 14th International Conference on Membrane Computing, Chişinău, August 20–23, 2013 (pp. 153–166). Academy of Sciences of Moldova: Institute of Mathematics and Computer Science.

Freund, R. (2016). P automata: New ideas and results. In: H. Bordihn, R. Freund, B. Nagy, Gy. Vaszil (eds.) Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29–30, 2016. Proceedings, [email protected], vol. 321, pp. 13–40. Österreichische Computer Gesellschaft

Freund, R. (2020). How derivation modes and halting conditions may influence the computational power of P systems. Journal of Membrane Computing, 2(1), 14–25. https://doi.org/10.1007/s41965-019-00028-9

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: A. Alhazov, S. Cojocaru, M. Gheorghe, Yu. Rogozhin, G. Rozenberg, A. Salomaa (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. (2007). Partial halting in P systems. Int. J. Found. Comput. Sci., 18(6), 1215–1225. https://doi.org/10.1142/S0129054107005261

Freund, R., Oswald, M. (2013). Catalytic and purely catalytic P automata: Control mechanisms for obtaining computational completeness. In: S. Bensch, F. Drewes, R. Freund, F. Otto (eds.) Fifth Workshop on Non-Classical Models for Automata and Applications – NCMA 2013, Umeå, Sweden, August 13 – August 14, 2013, Proceedings, [email protected], vol. 294, pp. 133–150. Österreichische Computer Gesellschaft

Freund, R., Oswald, M. (2017). Variants of spiking neural P systems with energy control. In: Proceedings of ICAROB 2017

Freund, R., Oswald, M., & Păun, Gh. (2015). Catalytic and purely catalytic P systems and P automata: control mechanisms for obtaining computational completeness. Fundam. Inform., 136(1–2), 59–84. https://doi.org/10.3233/FI-2015-1144.

Freund, R., Păun, Gh. (2013). How to obtain computational completeness in P systems with one catalyst. In: T. Neary, M. Cook (eds.) Proceedings Machines, Computations and Universality 2013, MCU 2013, Zürich, Switzerland, September 9–11, 2013. EPTCS, vol. 128, pp. 47–61 https://doi.org/10.4204/EPTCS.128.13

Freund, R., Păun, Gh., Pérez-Jiménez, M.J. (2007). Polarizationless P systems with active membranes working in the minimally parallel mode. In: S.G. Akl, C.S. Calude, M.J. Dinneen, G. Rozenberg, T. Wareham (eds.) Unconventional Computation, 6th International Conference, UC 2007, Kingston, Canada, August 13-17, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4618, pp. 62–76. Springer https://doi.org/10.1007/978-3-540-73554-0_8

Freund, R., Rogozhin, Yu., Verlan, S. (2012). P systems with minimal left and right insertion and deletion. In: J. Durand-Lose, N. Jonoska (eds.) Unconventional Computation and Natural Computation – 11th International Conference, UCNC 2012, Orléan, France, September 3–7, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7445, pp. 82–93. Springer https://doi.org/10.1007/978-3-642-32894-7_9

Freund, R., Sosík, P. (2015). On the power of catalytic P systems with one catalyst. In: G. Rozenberg, A. Salomaa, J.M. Sempere, C. Zandron (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

Freund, R., Verlan, S. (2007). A formal framework for static (tissue) P systems. In: G. Eleftherakis, P. Kefalas, Gh. Păun, G. Rozenberg, A. Salomaa (eds.) Membrane Computing, Lecture Notes in Computer Science, vol. 4860, pp. 271–284. Springer https://doi.org/10.1007/978-3-540-77312-2_17

Freund, R., & Verlan, S. (2011). (Tissue) P systems working in the k-restricted minimally or maximally parallel transition mode. Nat. Comput., 10(2), 821–833. https://doi.org/10.1007/s11047-010-9215-z

Krithivasan, K., Păun, Gh., & Ramanujan, A. (2014). On controlled P systems. Fundam. Inform. 131(3–4), 451–464 https://doi.org/10.3233/FI-2014-1025

Minsky, M. L. (1967). Computation. Englewood Cliffs: Finite and Infinite Machines. 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.): Handbook of Formal Languages. Springer (1997). https://doi.org/10.1007/978-3-642-59136-5

The P Systems Website. http://ppage.psystems.eu/

Thông tin
Thông tin xuất bản

Journal of Membrane Computing

Tập 3 Số 4

233-245

Thông tin tác giả