On the Number of Membranes in Unary P Systems

Rudolf Freund
Andreas Klein
Martin Kutrib

We consider P systems with a linear membrane structure working on objects over a unary alphabet using sets of rules resembling homomorphisms. Such a restricted variant of P systems allows for a unique minimal representation of the generated unary language and in that way for an effective solution of the equivalence problem. Moreover, we examine the descriptional complexity of unary P systems with respect to the number of membranes.

In Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, July 6-9, 2009, Electronic Proceedings in Theoretical Computer Science 3, pp. 101–109.
Published: 30th July 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.3.9 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org