Abstract
We investigate variants of the maximally and the minimally parallel transition mode, i.e., we allow only a bounded number of rules to be taken from every set of the partitioning of the whole set of rules. The 1-restricted minimally parallel transition mode especially fits to describe the way transitions take place in spiking neural P systems without delays, i.e., in every neuron where a rule is applicable exactly one rule has to be applied. Moreover, purely catalytic P systems working in the maximally parallel transition mode can be described as P systems using the corresponding rules without catalysts, i.e., noncooperative rules, when working in the 1-restricted minimally parallel transition mode. In contrast to these results for computationally complete models of P systems, with the k-restricted maximally parallel transition mode noncooperative rules only allow for the generation of semi-linear sets.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alhazov A, Freund R, Oswald M, Slavkovik M (2006) Extended spiking neural P systems generating strings and vectors of non-negative integers. In: Hoogeboom HJ, Păun Gh, Rozenberg G (eds) Pre-proceedings of membrane computing, international workshop, WMC7, Leiden, The Netherlands, 2006, pp 88–101
Bernardini F, Gheorghe M, Margenstern M, Verlan S (2007) Networks of cells and petri nets. In: Gutiérrez-Naranjo MA, Păun Gh, Romero-Jiménez A, Riscos-Núñez A (eds) Proceedings of fifth brainstorming week on membrane computing, Sevilla, 2007, pp 33–62
Ciobanu G, Pan L, Păun Gh, Pérez-Jiménez MJ (2007) P systems with minimal parallelism. Theor Comput Sci 378(1):117–130
Csuhaj-Varjú E (2001) Networks of language processors. In: Current trends in theoretical computer science, pp 771–790
Dassow J, Păun Gh (1999) On the power of membrane computing. J Univers Comput Sci 5(2):33–49
Freund R (2009) Transition and halting modes for tissue P systems. In: Păun Gh, Pérez-Jiménez MJ, Riscos-Núñez A (eds) Tenth workshop on membrane computing (WMC10), Curtea de Argeş, Romania, 24–27 August, 2009. RGNC REPORT 3/2009, Research Group on Natural Computing, Reports Universidad de Sevilla, pp 19–30
Freund R, Kogler M (2009) Hybrid transition modes in (tissue) P systems. In: Păun Gh, Pérez-Jiménez MJ, Riscos-N úñez A (eds) Tenth workshop on membrane computing (WMC10), Curtea de Argeş, Romania, 24–27 August, 2009. RGNC REPORT 3/2009, Research Group on Natural Computing, Reports Universidad de Sevilla, pp 228–239
Freund R, Verlan S (2007) A formal framework for P systems. In: Eleftherakis G, Kefalas P, Păun Gh (eds) Pre-proceedings of membrane computing. International workshop—WMC8, Thessaloniki, Greece, 2007, pp 317–330
Freund R, Verlan S (2008) P systems working in the k-restricted minimally parallel derivation mode. In: Csuhaj-Varjú E, Freund R, Oswald M, Salomaa K (eds) Proceedings of the international workshop on computing with biomolecules, Österreichische Computer Gesellschaft, Band 244, pp 43–52
Freund R, Kari L, Oswald M, Sosík (2005a) Computationally universal P systems without priorities: two catalysts are sufficient. Theor Comput Sci 330:251–266
Freund R, Păun Gh, Pérez-Jiménez MJ (2005b) Tissue-like P systems with channel states. Theor Comput Sci 330:101–116
Ibarra O, Yeng HC, Dang Z (2005) On various notions of parallelism in P systems. Int J Found Comput Sci 16(4):683–705
Ionescu M, Păun Gh, Yokomori T (2006) Spiking neural P systems. Fundam Inform 71(2–3):279–308
Korec I (1996) Small universal register machines. Theor Comput Sci 168:267–301
Păun Gh (1998) Computing with membranes. J Comput Syst Sci 61(1):108–143, and TUCS Research Report 208 (1998) (http://www.tucs.fi)
Păun Gh (2002) Membrane computing. An introduction. Springer, Berlin
Păun Gh, Yokomori T (1999) Membrane computing based on splicing. In: Winfree E, Gifford DK (eds) DNA based computers V, vol 54 of DIMACS series in discrete mathematics and theoretical computer science. American Mathematical Society, Providence, pp 217–232
Păun Gh, Sakakibara Y, Yokomori T (2002) P systems on graphs of restricted forms. Publ Mat 60:635–660
Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages (3 vols). Springer, Berlin
The P Systems Web Page: http://www.ppage.psystems.eu
Acknowledgements
The authors gratefully acknowledge the useful suggestions and remarks from Artiom Alhazov and Markus Beyreder.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Freund, R., Verlan, S. (Tissue) P systems working in the k-restricted minimally or maximally parallel transition mode. Nat Comput 10, 821–833 (2011). https://doi.org/10.1007/s11047-010-9215-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-010-9215-z