Affiliations: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. {lvalencia, dorellana, mdelamor, ariscosn, marper}@us.es
Correspondence:
[*]
Address for correspondence: Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
Abstract: Polarizationless P systems with active membranes are non-cooperative systems, that is, the left-hand side of their rules have a single object. Usually, these systems make use of division rules as a mechanism to produce an exponential workspace in linear time. Division rules are inspired by cell division, a process of nuclear division that occurs when a parent cell divides to produce two identical daughter cells. On the other hand, separation rules are inspired by the membrane fission process, a mechanism by which a biological membrane is split into two new ones in such a manner that the contents of the initial membrane is distributed between the new membranes. In this paper, separation rules are used instead of division rules. The computational efficiency of these models is studied and the role of the (minimal) cooperation in object evolution rules is explored from a computational complexity point of view.
Keywords: Membrane Fission, Membrane Computing, Active membranes, Separation rules, Complexity classes, SAT problem
