Wyniki wyszukiwania - BazTech

1

Small Universal Numerical P Systems with Thresholds for Computing Functions

Liu Liucheng, Yi Wenmei, Yang Qian, Peng Hong, Wang Jun

Fundamenta Informaticae

|

2020

|

Vol. 176, nr 1

43--59

EN

Abstracted from the nested structure of biological cells with application on the modeling of economical processes, numerical P systems (in short, NP systems) as a kind of distributed parallel computation systems have been proposed. It has been proven that NP systems and variants are Turing universal for number accepting/generating devices and language generating device. However, universality of NP systems as function computing devices has not been established. Aiming at numerical P systems with thresholds (in short, TNP systems), small universality for computing functions is discussed in this paper. Six small universal function computing devices of TNP systems for two threshold cases and working on three different modes are constructed, respectively.

2

P Systems with Rule Production and Removal

Pan Linqiang, Song Bosheng

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

313--329

EN

P systems are a class of parallel computational models inspired by the structure and functioning of living cells, where all the evolution rules used in a system are initially set up and keep unchanged during a computation. In this work, inspired by the fact that chemical reactions in a cell can be affected by both the contents of the cell and the environmental conditions, we introduce a variant of P systems, called P systems with rule production and removal (abbreviated as RPR P systems), where rules in a system are dynamically changed during a computation, that is, at any computation step new rules can be produced and some existing rules can be removed. The computational power of RPR P systems and catalytic RPR P systems is investigated. Specifically, it is proved that catalytic RPR P systems with one catalyst and one membrane are Turing universal; for purely catalytic RPR P systems, one membrane and two catalysts are enough for reaching Turing universality. Moreover, a uniform solution to the SAT problem is provided by using RPR P systems with membrane division. It is known that standard catalytic P systems with one catalyst and one membrane are not Turing universal. These results imply that rule production and removal is a powerful feature for the computational power of P systems.

3

The Computational Power of Cell-like P Systems with Symport/Antiport Rules and Promoters

Jiang Suxia, Wang Yanfeng, Xu Jinbang, Xu Fei

Fundamenta Informaticae

|

2019

|

Vol. 164, nr 2-3

207--225

EN

Cell-like P systems with symport/antiport rules (CSA P systems, for short) are a class of computational models in membrane computing, inspired by the way of transmembrane transport of substances through membrane channels between neighboring regions in a cell. In this work, we propose a variant of CSA P systems, called cell-like P systems with symport/antiport rules and promoters (CSAp P systems, for short), where symport/antiport rules are regulated by multisets of promoters. The computational power of CSAp P systems is investigated. Specifically, it is proved that CSAp P systems working in the maximally parallel mode, having arbitrary large number of membranes and promoters and using only symport rules of length 1 or antiport rules of length 2, are able to compute only finite sets of non-negative integers. Furthermore, we show that CSAp P systems with two membranes working in a sequential mode when having at most two promoters and using only symport rules of length 2, or having at most one promoter and using symport rules of length 1 and antiport rules of length 2, are Turing universal.

4

Handling Non-determinism in Spiking Neural P Systems : Algorithms and Simulations

Carandang Jym Paul, Cabarle Francis George C., Adorna Henry Natividad, Hernandez Nestine Hope S., Martínez-del-Amor Miguel Ángel

Fundamenta Informaticae

|

2019

|

Vol. 164, nr 2-3

139--155

EN

Spiking Neural P system is a computing model inspired on how the neurons in a living being are interconnected and exchange information. As a model in embrane computing, it is a non-deterministic and massively-parallel system. The latter makes GPU a good candidate for accelerating the simulation of these models. A matrix representation for systems with and without delay have been previously designed, and algorithms for simulating them with deterministic systems was also developed. So far, non-determinism has been problematic for the design of parallel simulators. In this work, an algorithm for simulating non-deterministic spiking neural P system with delays is presented. In order to study how the simulations get accelerated on a GPU, this algorithm was implemented in CUDA and used to simulate non-uniform and uniform solutions to the Subset Sum problem as a case study. The analysis is completed with a comparison of time and space resources in the GPU of such simulations.

5

Communication P Systems with Channel States Working in Flat Maximally Parallel Manner

Jiang Suxia, Wang Yanfeng, Xu Fei, Deng Junli

Fundamenta Informaticae

|

2019

|

Vol. 168, nr 1

1--24

EN

Communication P systems with channel states (CC P systems, for short) are a class of distributed parallel computing models, where communication (symport/antiport) rules associated with channel states are executed in a sequential manner on membrane channels. In this work, communication P systems with channel states working in flat maximally parallel manner are considered and the computational power is investigated. Specifically, it is proved that communication P systems with channel states using symport rules of length two are Turing universal when having one membrane and any number of channel states, or two membranes and three channel states. Furthermore, membrane division is introduced into communication P systems with channel states, communication P systems with channel states and membrane division (CCD P systems, for short) are proposed. We provide a uniform solution to the Hamiltonian path problem (HPP) by CCD P systems working in a flat maximally parallel manner.

6

Tissue P Systems with Small Cell Volume

Leporati A., Manzoni L., Mauri G., Porreca A. E., Zandron C.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

261--275

EN

Traditionally, P systems allow their membranes or cells to grow exponentially (or even more) in volume with respect to the size of the multiset of objects they contain in the initial configuration. This behaviour is, in general, biologically unrealistic, since large cells tend to divide in order to maintain a suitably large surface-area-to-volume ratio. On the other hand, it is usually the number of cells that needs to grow exponentially with time by binary division in order to solve NP-complete problems in polynomial time. In this paper we investigate families of tissue P systems with cell division where each cell has a small volume (i.e., sub-polynomial with respect to the input size), assuming that each bit of information contained in the cell, including both those needed to represent the multiset of objects and the cell label, occupies a unit of volume. We show that even a constant volume bound allows us to reach computational universality for families of tissue P systems with cell division, if we employ an exponential-time uniformity condition on the families. Furthermore, we also show that a sub-polynomial volume does not suffice to solve NP-complete problems in polynomial time, unless the satisfiability problem for Boolean formulae can be solved in sub-exponential time, and that solving an NP-complete problem in polynomial time with logarithmic cell volume implies P = NP.

7

Spiking Neural P Systems with Rules on Synapses Working in Sum Spikes Consumption Strategy

Su Y., Wu T., Xu F., Păun A.

Fundamenta Informaticae

|

2017

|

Vol. 156, nr 2

187--208

EN

Spiking neural P systems with rules on synapses (RSSN P systems, for short) are a class of distributed and parallel computation models inspired by the way in which neurons process and communicate information with each other by means of spikes, where neurons only contain spikes and the evolution rules are on synapses. RSSN P systems have been proved to be Turing universal, using the strategy that restricts all the applied rules to consume the same number of spikes from the given neuron, termed as equal spikes consumption strategy. In this work, in order to avoid imposing the equal spikes consumption restriction on the application of rules, a new strategy for rule application, termed as sum spikes consumption strategy, is considered in RSSN P systems, where a maximal set of enabled rules from synapses starting from the same neuron is nondeterministically chosen to be applied, in the sense that no further synapse can use any of its rules, and the sum of these numbers of spikes that all the applied rules consume is removed from the neuron. In this way, the proposed strategy avoids checking whether all the applied rules consume the same number of spikes from the given neuron. The computation power of RSSN P systems working in the proposed strategy is investigated, and it is proved that such systems characterize the semilinear sets of natural numbers, i.e., such systems are not universal. Furthermore, RSSN P systems with weighted synapses working in the proposed strategy are proved to be Turing universal. These results show that the weight on synapses is a powerful ingredient of RSSN P systems in terms of the computation power, which makes RSSN P systems working in sum spikes consumption strategy become universal from non-universality.

8

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.

9

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.

10

A Note on Spiking Neural P Systems with Homogenous Neurons and Synapses

Yu Y., Wu T., Xu J., Wang Y., He J.

Fundamenta Informaticae

|

2017

|

Vol. 150, nr 2

231--240

EN

Spiking neural (SN, for short) P systems are a class of computation models inspired from the way in which neurons communicate by exchanging spikes. SN P systems with homogenous neurons and synapses are a new variant of SN P systems, where the spiking and forgetting rules are placed on synapses instead of in neurons and each synapse has the same set of spiking and forgetting rules. Recent studies illustrated that this variant of SN P systems is Turing universal as both number generating and accepting devices. In this note, we prove that SN P systems with homogenous neurons and synapses without the feature of delay are also Turing universal. This result gives a positive answer to an open problem formulated in [K. Jiang, et al. Neurocomputing 171(2016) 1548-1555] “whether SN P systems with homogenous neurons and synapses are Turing universal when the feature of delay is not used”.

11

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).

12

Small Universal Spiking Neural P Systems with Homogenous Neurons and Synapses

Wu T., Wang Y., Jiang S., Shi X.

Fundamenta Informaticae

|

2016

|

Vol. 149, nr 4

451--470

EN

Spiking neural (SN, for short) P systems are a class of distributed parallel computing models inspired by the way in which neurons communicate with each other by means of electrical impulses. Recently, a new variant of SN P systems, called SN P systems with homogenous neurons and synapses (HRSSN P systems for short) was proposed, where the spiking and forgetting rules are placed on synapses instead of in neurons and each synapse has the same set of spiking and forgetting rules. This variant of SN P systems has already been proved to be Turing universal as both number generating and accepting devices. In this work, we consider the problem of looking for small universal HRSSN P systems. Specifically, a universal HRRSN P system with standard rules and weight at most 5 having 70 neurons is constructed as a device of computing functions; as a number generator, we find a universal system with standard rules and weight at most 5 having 71 neurons.

13

On the Universality of Colored One-Catalyst P Systems

Wu T., Zhang Z., Paun G., Pan L.

Fundamenta Informaticae

|

2016

|

Vol. 144, nr 2

205--212

EN

A control strategy on the computations in a one-catalyst P system is provided: the rules are assumed “colored” and in each step only rules of the same “color” are used. Such control leads to Turing universality for one-catalyst P systems with one membrane. Turing universality is also reached for purely catalytic P systems with two catalysts, and for purely catalytic P systems with only one catalyst and cooperating rules working in the so-called terminal mode.

14

On a workflow model based on generalized communicating P systems

Balasko A.

Computer Science

|

2016

|

Vol. 17 (1)

45--68

EN

This paper introduces a new formal mathematical model for investigating work- flows from dynamical and behavioural point of view. The model is designed on the basis of a special variant of the biology-inspired formal computational model called membrane systems, where the jobs or services are represented by membrane objects whose behaviour is defined by communication and generalization rules. The model supports running computations in a massive parallel manner, which makes it ideal to model high throughput workflow interpreters. Among the variants introduced in the literature, we have selected the Generalized Communicating P Systems, as it focuses on the communication among the membranes. Most of the workflow languages, based on different formal models like Petri nets or Communicating Sequential Processes, support several predefined structures – namely workflow patterns – to control the workflow interpretation such as conditions, loops etc. In this paper we show how these patterns are adapted into the membrane environment which, taking into account that membrane systems can be used to study complex dynamic systems’ runtime behaviour, makes this model a relevant alternative for the current models.

15

Uniform Solution to Common Algorithmic Problem by P Systems Working in the Minimally Parallel Mode

Niu Y., Venkat I., Khader A. T., Subramanian K. G.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 3

285--296

EN

It is known that the Common Algorithmic Problem (CAP) has the nice property that several other NP-complete problems can be reduced to it in linear time. The decision version of this problemis known to be efficiently solved by a family of recognizer P systems with activemembranes with three electrical charges working in the maximally parallel way. We here work with a variant of P systems with active membranes without polarizations and present a uniform solution to CAP in the minimally parallel mode.

16

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.

17

Relating Computations in Non-cooperative Transition P Systems and Evolution-Communication P Systems with Energy

Juayong R. A. B., Adorna H. N.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 3

209--217

EN

This paper explores the relation of computations in Evolution-Communication P systems with energy (ECPe systems) and non-cooperative Transition P systems without dissolution (TP systems). We have shown that for every non-cooperative TP system, we can construct an ECPe system that, (i) generates the same language, and (ii) each halting computation that takes τ steps in the TP system can be simulated in at most 3τ + 1 steps in its corresponding ECPe system.τ

18

On String Languages Generated by Spiking Neural P Systems with Astrocytes

Kong Y., Zhang Z., Liu Y.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 3

231--240

EN

Spiking neural P systems with astrocytes (SNPA systems, for short) are a class of distributed parallel computing devices inspired from the way spikes pass along the synapses between neurons. In this work, we investigate the computational power of SNPA systems as language generators. Specifically, representations of recursively enumerable languages and of regular languages are given by means of SNPA systems without forgetting rules. Furthermore, a simple finite language is produced which can be generated by SNPA systems, while it cannot be generated by usual spiking neural P systems. These results show that the astrocytes are a powerful ingredient for spiking neural P systems as language generators.

19

Membrane Division, Oracles, and the Counting Hierarchy

Leporati A., Manzoni L., Mauri G., Porreca A. E., Zandron C.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

97--111

EN

Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to PPP = P#P, the class of problems solvable in polynomial time by deterministic Turingmachines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between PPP and PSPACE. In particular, for each integer k ≥ 0 we provide a lower bound to the computing power of P systems of depth k.

20

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.