IMCS/Publications/CSJM/Issues/CSJM v.23, n.3 (69), 2015/

Small P Systems with Catalysts or Anti-Matter Simulating Generalized Register Machines and Generalized Counter Automata

Authors: Alhazov Artiom, Rudolf Freund, Petr Sosík


In this paper we focus on two weak forms of cooperation in P systems, namely, catalytic rules and matter/anti-matter annihilation rules. These variants of P systems both are computationally complete, while the corresponding rule complexity turns out to be of special interest. For establishing considerably small universal P systems in both cases, we found two suitable tools: generalized register machines and generalized counter automata. Depending on the features used in the different variants, we construct several small universal P systems.

Artiom Alhazov
Institute of Mathematics and Computer Science
Str. Academiei 5, Cișinău, MD-2028, Moldova

Rudolf Freund
Faculty of Informatics, TU Wien
Favoritenstrass{}e 9-11, 1040 Wien, Austria

Petr Sosík
Research Institute of the IT4Innovations Centre of Excellence
Faculty of Philosophy and Science, Silesian University in Opava
74601 Opava, Czech Republic

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License


Adobe PDF document0.17 Mb