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

Tissue P Systems with Protein on Cells

Song B., Pan L., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2016

|

Vol. 144, nr 1

77--107

EN

Tissue P systems are a class of distributed parallel computing devices inspired by biochemical interactions between cells in a tissue-like arrangement, where objects can be exchanged by means of communication channels. In this work, inspired by the biological facts that the movement of most objects through communication channels is controlled by proteins and proteins can move through lipid bilayers between cells (if these cells are fused), we present a new class of variant tissue P systems, called tissue P systems with protein on cells, where multisets of objects (maybe empty), together with proteins between cells are exchanged. The computational power of such P systems is studied. Specifically, an efficient (uniform) solution to the SAT problem by using such P systems with cell division is presented. We also prove that any Turing computable set of numbers can be generated by a tissue P system with protein on cells. Both of these two results are obtained by such P systems with communication rules of length at most 4 (the length of a communication rule is the total number of objects and proteins involved in that rule).

4

Simulating P Systems on GPU Device : A Survey

Martínez-del-Amor M. A., García-Quismondo M., Macías-Ramos L. F., Valencia-Cabrera L., Riscos-Núñez A., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 3

269--284

EN

P systems have been proven to be useful as modeling tools in many fields, such as Systems Biology and Ecological Modeling. For such applications, the acceleration of P system simulation is often desired, given the computational needs derived from these kinds of models. One promising solution is to implement the inherent parallelism of P systems on platforms with parallel architectures. In this respect, GPU computing proved to be an alternative to more classic approaches in Parallel Computing. It provides a low cost, and a manycore platform with a high level of parallelism. The GPU has been already employed to speedup the simulation of P systems. In this paper, we look over the available parallel P systems simulators on the GPU, with special emphasis on those included in the PMCGPU project, and analyze some useful guidelines for future implementations and developments.

5

Extending Simulation of Asynchronous Spiking Neural P Systems in P–Lingua

Macías-Ramos L. F., Pérez-Jiménez M. J., Song T., Pan L.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 3

253--267

EN

Spiking neural P systems (SN P systems for short) are a class of neural-like computing models in the framework of membrane computing. Inspired by the neurophysiological structure of the brain, SN P systems have been extended in various ways. P–Lingua is a standard language for the definition of P systems, where pLinguaCore library provides particular implementations of parsers and simulators for the models specified in P–Lingua. A support for simulating SN P systems in P–Lingua was introduced recently and soon expanded to cover further features of these systems. In this paper, we present an extension of P–Lingua related to asynchronous SN P systems, in order to incorporate simulation capabilities for limited asynchronous SN P systems and asynchronous SN P systems with local synchronization.

6

An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation

Pérez-Jiménez M. J., Sosík P.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

45--60

EN

A membrane system (P system) is a distributed computingmodel inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderline: passing from length 2 to 3 amounts to passing from non–efficiency to efficiency, assuming that P 6= NP.

7

A P–Lingua Based Simulator for P Systems with Symport/Antiport Rules

Macías-Ramos L. F., Valencia-Cabrera L., Song B., Song T., Pan L., Pérez-Jiménez M. J.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 2

211--227

EN

Inspired by mitosis process and membrane fission processes, cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules have been introduced, respectively. These computation systems have two key features: the ability to have infinite copies of some objects (within an active environment) and to generate an exponential workspace in polynomial time. In this work, we extend the P-Lingua framework for simulating that kind of P systems taking into account these two features. Consequently, a new simulator has been developed and included in pLinguaCore library. The functioning of the simulator has been checked by simulating efficient solutions to SAT problem using a family of cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules. The corresponding MeCoSim based application is also provided.

8

Bridging Membrane and Reaction Systems : Further Results and Research Topics

Păun G., Pérez-Jiménez M.J., Rozenberg G.

Fundamenta Informaticae

|

2013

|

Vol. 127, nr 1-4

99--114

EN

This paper continues an investigation into bridging two research areas concerned with natural computing: membrane computing and reaction systems. More specifically, the paper considers a transfer of two assumptions/axioms of reaction systems, non-permanency and the threshold assumption, into the framework of membrane computing. It is proved that: (1) spiking neural P systems with non-permanency of spikes assumption characterize the semilinear sets of numbers, and (2) symport/antiport P systems with threshold assumption (translated as ω multiplicity of objects) can solve SAT in polynomial time. Also, several open research problems are stated.

9

Spiking Neural dP Systems

Ionescu M., Paun G., Pérez-Jiménez M.J., Yokomori T.

Fundamenta Informaticae

|

2011

|

Vol. 111, nr 4

423-436

EN

We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which “read” strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open.

10

Looking for Small Efficient P Systems

Pérez-Jiménez M.J., Rius-Font M., Riscos-Nunez A., Romero-Campero F. J.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

293-308

EN

In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework ofMembrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper.

11

A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem

Niu Y., Pan L., Pérez-Jiménez M.J., Font M. R.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 2

179-188

EN

A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NPcomplete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules.

12

On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution

Zandron C., Leporati A., Ferretti C., Mauri G., Pérez-Jiménez M.J.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 1

79-91

EN

Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximallly parallel way.

13

Editing Configurations of P Systems

Csuhaj-Varjú E., Di Nola Di, Paun G., Pérez-Jiménez M.J., Vaszil G.

Fundamenta Informaticae

|

2008

|

Vol. 82, nr 1-2

29-46

EN

This paper proposes and investigates the possibility of transforming a configuration of a P system (the membrane structure and the multisets of symbol-objects present in the compartments) into another configuration by means of a given set of rules to be applied to the membranes and to the multisets of objects. Although this transformation is obtained during the computation in a P system, we consider it as a goal per se, as a pre-computation phase, when the system itself is built. In this framework, several important problems appear: the edit-distance between configurations (with respect to a given set of editing rules), normal forms, the reachability of configurations, or the existence of single configurations from which a given family of configurations can be constructed, only to mention a few. We investigate here some of these questions; the paper is mainly devoted to formulating problems in the new framework, to calling attention to the possible extensions and the usefulness of the present approach.

14

On String Languages Generated by Spiking Neural P Systems

Chen H., Freund R., Ionescu M., Paun G., Pérez-Jiménez M.J.

Fundamenta Informaticae

|

2007

|

Vol. 75, nr 1-4

141-162

EN

We continue the study of spiking neural P systems by considering these computing devices as binary string generators: the set of spike trains of halting computations of a given system constitutes the language generated by that system. Although the "direct" generative capacity of spiking neural P systems is rather restricted (some very simple languages cannot be generated in this framework), regular languages are inverse-morphic images of languages of finite spiking neural P systems, and recursively enumerable languages are projections of inverse-morphic images of languages generated by spiking neural P systems.

15

On the Branching Complexity of P Systems

Ciobanu G., Paun G., Pérez-Jiménez M.J.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

27-36

EN

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.

16

Symport/Antiport P Systems with Three Objects Are Universal

Păun G., Pérez-Jiménez M. J., Pazos J., Rodriguez-Patón A.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

353-367

EN

The operations of symport and antiport, directly inspired from biology, are already known to be rather powerful when used in the framework of P systems. In this paper we confirm this observation with a quite surprising result: P systems with symport/antiport rules using only three objects can simulate any counter machine, while systems with only two objects can simulate any blind counter machine. In the first case, the universality (of generating sets of numbers) is obtained also for a small number of membranes, four.

17

Simulating Turing Machines by P Systems with External Output

Romero-Jiménez A., Pérez-Jiménez M.J.

Fundamenta Informaticae

|

2002

|

Vol. 49, nr 1-3

273-287

EN

In [3] a variant of the computation model introduced by Gh. Pun in [1] is considered: membrane systems with external output, which were proven to be universal, in the sense that they are able to generate all Parikh images of recursively enumerable languages. Here we give another proof of the universality of this model. The proof is carried out associating to each deterministic Turing machine a P system with external output that simulates its running. Thus, although we work with symbol-objects, we get strings as a result of computations, and in this way we generate directly all recursively enumerable languages, instead of their images through Parikh mapping, as it is done in [3].