On the branching complexity of P systems

TitleOn the branching complexity of P systems
Publication TypeJournal Papers
Year of Publication2006
AuthorsCiobanu, G., Paun G., & Pérez-Jiménez M. J.
Journal TitleFundamenta Informaticae
PublisherIOS Press
Place PublishedAmsterdam, Holanda

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.

Keywordsdecidability, descriptional complexity, Membrane computing, non-determinism