Variants of Small Universal P Systems with Catalysts

• Autorzy: Alhazov A. , Freund R.

Identyfikatory

DOI

10.3233/FI-2015-1209

• Języki publikacji: EN

Abstrakty

EN

Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky’s reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we are able to transformthe universalmachines U₂₂ and U₂₀ of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result.

Słowa kluczowe

EN

computational complexity; completeness theorem; catalysts; machine theory; problem solving

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 227--250
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Alhazov A.

• Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chisinau, MD-2028, Moldova

autor

Freund R.

• Faculty of Informatics Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria

Bibliografia

• [1] A. Alhazov, B. Aman, R. Freund, Gh. Păun: Matter and Anti-Matter inMembrane Systems. In: H. Jürgensen, J. Karhumäki, A. Okhotin (Eds.): 16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014, Lecture Notes in Computer Science 8614, 2014, 65–76.
• [2] A. Alhazov, R. Freund: Small P Systems Defining Non-semilinear Sets. Emergence, Complexity and Computation 12, Automata, Universality, Computation (A. Adamatzky, Ed.), Springer, 2015, 183–217.
• [3] A. Alhazov, R. Freund: P Systems with Toxic Objects. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P Sosık, C. Zandron (Eds.): Membrane Computing – 15th InternationalConference, CMC 2014, Prague, Czech Republic, August 2022, 2014, Revised Selected Papers. Lecture Notes in Computer Science 8961, Springer, 2014, 99-125.
• [4] A. Alhazov, M. Kudlek, Yu. Rogozhin: Nine Universal Circular Post Machines. Computer Science Journal of Moldova 10 (3), 247–262 (2002).
• [5] A. Alhazov, Yu. Rogozhin, S. Verlan: On Small Universal Splicing Systems. International Journal of Foundations of Computer Science 23 (7), 1423–1438 (2012).
• [6] A. Alhazov, D. Sburlan: Static Sorting P Systems. In: G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez (Eds.): Applications of Membrane Computing, Natural Computing Series, Springer, 2005, 215–252.
• [7] A. Alhazov, S. Verlan: Minimization Strategies forMaximally ParallelMultiset Rewriting Systems. Theoretical Computer Science 412 (17), 1581–1591 (2011).
• [8] R. Freund, L. Kari, M. Oswald, P. Sos´ık: Computationally Universal P Systems without Priorities: Two Catalysts Are Sufficient. Theoretical Computer Science 330 (2), 251–266 (2005).
• [9] R. Freund, A. Leporati, G. Mauri, A.E. Porreca, S. Verlan, C. Zandron: Flattening in (Tissue) P Systems. In: A. Alhazov, S. Cojocaru, M. Gheorghe, Yu. Rogozhin, G. Rozenberg, A. Salomaa (Eds.): Membrane Computing – 14th International Conference, CMC 2013, Chis¸inău, Republic of Moldova, August 20–23, 2013, Revised Selected Papers. Lecture Notes in Computer Science 8340, Springer, 2014, 173–188.
• [10] R. Freund, M. Oswald: Small Universal Antiport P Systems and Universal Multiset Grammars. In: M.A. Gutiérrez-Naranjo, Gh. Păun, A. Riscos-N´u˜nez, F.J. Romero-Campero (Eds.): Fourth Brainstorming Week on Membrane Computing, Sevilla, 2006, vol. II, RGNC Report 03/2006, Fénix Editora, Sevilla, 2006, 51–64.
• [11] R. Freund, M. Oswald: A Small Universal Antiport P System with Forbidden Context. In: H. Leung, G. Pighizzini (Eds.): Proceedings of the 8th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2006, Las Cruces, New Mexico, USA, 2006, New Mexico State University, 2006, 259–266.
• [12] S. Ivanov, E. Pelz, S. Verlan: Small Universal Non-deterministic Petri Nets with Inhibitor Arcs. In: H. Jürgensen, J. Karhum¨aki, A. Okhotin (Eds.): 16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014, Lecture Notes in Computer Science 8614, 2014, 186–197.
• [13] I. Korec: Small Universal Register Machines. Theoretical Computer Science 168, 1996, 267–301.
• [14] M. Kudlek, Yu. Rogozhin: Small Universal Circular Post Machines. Computer Science Journal of Moldova 9 (1), 34–52 (2001).
• [15] M.L. Minsky: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, USA, 1967.
• [16] Gh. Păun: Computing with Membranes. Journal of Computer and System Sciences 61 (1), 108–143 (2000) (and Turku Center for Computer Science – TUCS Report 208, November 1998, www.tucs.fi).
• [17] Gh. Păun: Membrane Computing. An Introduction. Springer, 2002.
• [18] Gh. Păun, G. Rozenberg, A. Salomaa: The Oxford Handbook of Membrane Computing. Oxford University Press, 2010.
• [19] Yu. Rogozhin: Small Universal Turing Machines. Theoretical Computer Science 168 (2), 215–240 (1996).
• [20] Yu. Rogozhin: A Universal TuringMachine with 22 States and 2 Symbols. Romanian Journal of Information Science and Technology 1 (3), 259–265 (1998).
• [21] G. Rozenberg, A. Salomaa (Eds.): Handbook of Formal Languages, 3 volumes. Springer, 1997.
• [22] P. Sosık, M. Langer: Improved Universality Proof for Catalytic P Systems and a Relation to Non-Semilinear Sets. In: S. Bensch, R. Freund, F. Otto (Eds.): Sixth Workshop on Non-Classical Models of Automata and Applications (NCMA 2014), [e-mail], BAND 304, 2014, 223–233.
• [23] D. Woods, T. Neary: Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines. Fundamenta Informaticae, this volume.
• [24] P systems webpage. http://ppage.psystems.eu.