Wyniki wyszukiwania - BazTech

1

Cooperation in Transport of Chemical Substances : A Complexity Approach within Membrane Computing

Valencia-Cabrera L., Orellana-Martín D., Martínez-del-Amor M. A., Riscos-Núñez A., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

373--385

EN

Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P. P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP-complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted.

2

Computational Efficiency of Minimal Cooperation and Distribution in Polarizationless P Systems with Active Membranes

Valencia-Cabrera L., Orellana-Martín D., Martínez-del-Amor M. A., Riscos-Núñez A., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 1/2

147--172

EN

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.

3

Sevilla Carpets Revisited : Enriching the Membrane Computing Toolbox

Orellana-Martín D., Graciani C., Macías-Ramos L.-F., Martínez-del-Amor M. A., Riscos-Núñez A., Romero-Jiménez A., Valencia-Cabrera L.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

153--166

EN

Sevilla carpets have already been used to compare different solutions of the Subset Sum problem: either designed in the framework of P systems with active membranes (both in the case of membrane division and membrane creation), and in the framework of tissue-like P systems with cell division. Recently, the degree of parallelism and other descriptive complexity details have been found to be relevant when designing parallel simulators running on GPUs. We present here a new way to use the information provided by Sevilla carpets in this context, and a script that allows to generate them automatically from P-Lingua files.