Partial Halting and Minimal Parallelism Based on Arbitrary Rule Partitions

• Autorzy: Alhazov A. , Oswald M. , Freund R. , Verlan S.
• Języki publikacji: EN

Abstrakty

EN

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.

Słowa kluczowe

EN

computational completeness; halting; minimal parallelism; P systems; permitting context

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 17--34
• Opis fizyczny: bibliogr. 25 poz., tab.

Twórcy

autor

Alhazov A.

autor

Oswald M.

autor

Freund R.

autor

Verlan S.

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

Bibliografia

• [1] A. Alhazov: On determinismof evolution-communicationP systems, Journal of Universal Computer Science 10 (5) (2004), 502-508.
• [2] A. Alhazov, Number of protons/bi-stable catalysts and membranes in P systems. Time-freeness. In: [14], 79-95.
• [3] A. Alhazov: Communication in Membrane Systems with Symbol Objects. Ph.D. Thesis, Tarragona, Spain, 2006.
• [4] A. Alhazov, R. Freund, M. Oswald, S. Verlan: Partial versus total halting in P systems. In: M.A. Gutiérrez-Naranjo, Gh. Păun, A. Romero-Jiménez, and A. Riscos-Nuñez (Eds.), Proceedings of the Fifth Brainstorming Week on Membrane Computing, Sevilla (Spain), January 29th - February 2, 2007,1-20.
• [5] A. Alhazov, R. Freund,M. Oswald, S. Verlan: Partial halting in P systems using membrane rules with permitting contexts. In: J.O. Durand-Lose,M. Margenstern (Eds.): Machines, Computations, and Universality, 5th International Conference, MCU 2007, Orlans, France, September 10-13, 2007, Proceedings. Lecture Notes in Computer Science 4664, Springer, 2007, 110-121.
• [6] F. Bernardini, V. Manca: P systems with boundary rules. In: [21], 107-118.
• [7] F. Bernardini, F. J. Romero-Campero, M. Gheorghe, M.J. Pérez-Jiménez, M. Margenstern, S. Verlan, N. Krasnogor: On P systems with bounded parallelism. In: G. Ciobanu, Gh. Păun (Eds.): Pre-Proc. of First International Workshop on Theory and Application of P Systems, Timisoara, Romania, September 26-27, 2005, 31-36.
• [8] M. Cavaliere: Evolution-communication P systems. In: [21], 134-145.
• [9] G. Ciobanu, L. Pan, Gh. Păun, M.J. Pérez-Jiménez: P systems with minimal parallelism, Theoretical Computer Science 378 (1) (2007), 117-130.
• [10] J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory. Springer, Berlin, 1989.
• [11] J. Dassow, Gh. Păun: On the power of membrane computing, Journal of Universal Computer Science 5 (2) (1999), 33-49.
• [12] R. Freund, M. Oswald: P Systems with activated/prohibited membrane channels. In: [21], 261-268.
• [13] R. Freund, M. Oswald: Partial halting in P systems, Intern. J. Found. Computer Sci. 18 (6) (2007), 1215-1225.
• [14] R. Freund, Gh. Păun, G. Rozenberg, A. Salomaa (Eds.): Membrane Computing. 6th InternationalWorkshop WMC 2005, Vienna, Austria, Lecture Notes in Computer Science 3850, Springer, 2006.
• [15] R. Freund, Gh. Păun, M.J. Pérez-Jiménez: Tissue-like P systems with channel states, Theoretical Computer Science 330 (2005), 101-116.
• [16] R. Freund, S. Verlan: A formal framework for static (tissue) P systems. In: G. Eleftherakis, P. Kefalas, Gh. Păun, G. Rozenberg, A. Salomaa (Eds.): Membrane Computing, 8th International Workshop, WMC 2007, Thessaloniki, Greece, June 25-28, 2007. Revised Selected and Invited Papers, Lecture Notes in Computer Science 4860, Springer, Berlin, 271-284.
• [17] M.L. Minsky: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, USA, 1967.
• [18] A. Păun, Gh. Păun: The power of communication: P systems with symport/ antiport, New Generation Computing 20, 3 (2002), 295-306.
• [19] Gh. Păun: Computing with membranes, J. of Computer and System Sciences 61, 1 (2000), 108-143, and TUCS Research Report 208 (1998) (http://www.tucs.fi).
• [20] Gh. Păun: Membrane Computing. An Introduction. Springer, Berlin, 2002.
• [21] Gh. Păun, G. Rozenberg, A. Salomaa, C. Zandron (Eds.): Membrane Computing. International Workshop WMC 2002, Curteă de Arges¸, Romania, Revised Papers. Lecture Notes in Computer Science 2597, Springer, Berlin, 2003.
• [22] Y. Rogozhin, A. Alhazov, R. Freund: Computational power of symport/antiport: history, advances, and open problems. In: [14], 1-30.
• [23] G. Rozenberg, A. Salomaa (Eds.): Handbook of Formal Languages (3 volumes). Springer, Berlin, 1997.
• [24] S. Verlan, F. Bernardini,M. Gheorghe,M. Margenstern: On communication in tissue P systems: conditional uniport. Pre-proceedings of Membrane Computing. International Workshop, WMC7, Leiden, The Netherlands, 2006, 507-521.
• [25] The P Systems Web Page: http://ppage.psystems.eu/