Trading polarizations for labels in P systems with active membranes

TitleTrading polarizations for labels in P systems with active membranes
Publication TypeJournal Papers
Year of Publication2004
AuthorsAlhazov, A., Pan L., & Paun G.
Journal TitleActa Informatica
PublisherSpringer Verlag
Place PublishedAmsterdam, Netherlands
Volume41
Pages111-144
Abstract

This paper addresses the problem of removing the polarization of membranes from P systems with active membranes - and this is achieved by allowing the change of membrane labels by means of communication rules or by membrane dividing rules. As consequences of these results, we obtain the universality of P systems with active membranes which are allowed to change the labels of membranes, but do not use polarizations. Universality results are easily obtained also by direct proofs. By direct constructions, we also prove that SAT can be solved in linear time by systems without polarizations and with label changing possibilities. If non-elementary membranes can be divided, then SAT can be solved in linear time without using polarizations and label changing. Several open problems are also formulated.

URLhttp://www.springerlink.com/index/A7HGMKPDA0W7F0W2.pdf
Issue2-3
ISSN Number0001-5903
DOI10.1007/s00236-004-0153-z
AttachmentSize
Trading polarizations for Labels....pdf282.13 KB