On the Branching Complexity of P Systems

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Ciobanu, Gabriel | Păun, Gheorghe | Pérez-Jiménez, Mario J.

Affiliations: Romanian Academy, Institute of Computer Science Bd. Copou 8, 700506 Iaşi, Romania. E-mail: gabriel@iit.tuiasi.ro | Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucureşti, Romania. E-mails: george.paun@imar.ro; gpaun@us.es | Department of Computer Science and AI, University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. E-mail: marper@us.es

Abstract: 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.

Keywords: Membrane computing, non-determinism, descriptional complexity, decidability

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 27-36, 2006