On the Branching Complexity of P Systems

• Autorzy: Ciobanu G. , Paun G. , Pérez-Jiménez M.J.
• Języki publikacji: EN

Abstrakty

EN

We consider two complexity parameters related to the graph of reachable configurations of a given P system, namely the outdegree as a measure of the degree of non-determinism, and the indegree as a measure of the degree of confluence. These parameters can be defined for both the generative and the accepting mode of using a P system. We investigate here these parameters in what concerns hierarchies and decidability issues. We prove that all hierarchies have only two levels and that all considered decidability problems have a negative answer.

Słowa kluczowe

EN

membrane computing; nondeterminism; descriptional complexity; decidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 27--36
• Opis fizyczny: bibliogr. 10 poz.

Twórcy

autor

Ciobanu G.

autor

Paun G.

autor

Pérez-Jiménez M.J.

• Institute of Mathematics of the Romanian Academy, PO Box 1 - 764, 70700 Bucuresti, Romania,

Bibliografia

• [1] A. Alhazov: Maximally parallel multiset-rewriting systems. Browsing the configurations. Proceedings of Third Brainstorming Week on Membrane Computing, Sevilla, 2005, Report No. 01/2005 of Research Group on Natural Computing, Sevilla University, 2005, 1-10.
• [2] A. Alhazov,M. Margenstern, V. Rogozhin, Y. Rogozhin, S. Verlan: Communicative P systems with minimal cooperation. In Membrane Computing. International Workshop WMC5, Milan, Italy, 2004. Revised Papers (G. Mauri et al., eds.), LNCS 3365, Springer, Berlin, 2005, 162-178.
• [3] J. Dassow, Gh. P˘aun: On the succinctness of descriptions of context-free languages by cooperating distributed grammar systems. Computers and AI, 10 (1991), 513-527.
• [4] R. Freund, Gh. P˘aun: On deterministic P systems. Submitted, 2004 (available at [10]).
• [5] J. Gruska: Descriptional complexity of context-free languages. Proc. Math. Found. Computer Sci. Conf., High Tatras, 1973, 71-83.
• [6] O.H. Ibarra: On determinism versus nondeterminism in P systems. Theoretical Computer Sci., to appear.
• [7] M.L. Minsky: Computation. Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967.
• [8] A. Pǎun, Gh. Pǎun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295-306.
• [9] Gh. Pǎun: Membrane Computing. An Introduction. Springer, Berlin, 2002.
• [10] The P Systems Web Address: http://psystems.disco.unimib.it