Wyniki wyszukiwania - BazTech

1

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.

2

Weighted Spiking Neural P Systems with Rules on Synapses

Zhang X., Zeng X., Pan L.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

201--218

EN

Spiking neural P systems (SN P systems, for short) with rules on synapses are a new variant of SN P systems, where the spiking and forgetting rules are placed on synapses instead of in neurons. Recent studies illustrated that this variant of SN P systems is universal working in the way that the synapses starting from the same neuron work in parallel (i.e., all synapses starting from the same neuron should apply their rules if they have rules to be applied). In this work, we consider SN P systems with rules on synapses working in another way: the synapses starting from the same neuron are restricted to work in a sequential way (i.e., at each step at most one synapse starting from the same neuron applies its rule). It is proved that the computational power of SN P systems with rules on synapses working in this way is reduced; specifically, they can only generate finite sets of numbers. Such SN P systems with rules on synapses are proved to be universal, if synapses are allowed to have weight at most 2 (if a rule which can generate n spikes is applied on a synapse with weight k, then the neuron linking to this synapse will receive totally nk spikes). Two small universal SN P systems with rules on synapses for computing functions are also constructed: a universal system with 26 neurons when using extended rules and each synapse having weight at most 2, and a universal system with 26 neurons when using standard rules and each synapse having weight at most 12. These results illustrate that the weight is an important feature for the computational power of SN P systems.

3

Three Universal Homogeneous Spiking Neural P Systems Using Max Spike

Păun A., Sosík P.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

167--182

EN

We improve and extend a recent result showing that spiking neural P systems with the same rules in all neurons of the system (homogenous) and working in the max sequential manner are universal. The previous work in this area reported by the group led by Dr. Linqiang Pan did not put any bound on the number of neurons used. We believe this is an important question for any future practical implementation of such systems that deserves investigation, and we provide some results in this direction. Extending the aforementioned construction with the work of Korec on small register machines one could estimate the size of the previous construction at 105 neurons. We are able to improve this result and to show that an SNP system with 83 neurons having homogenous rules and working in the max sequential manner is universal. Several related results with respect to max-pseudo sequentiality mode are also obtained: 83 neurons are necessary for this case, too. When considering the case of systems without weighted synapses, we show that one needs at most 244 homogenous neurons for reaching universality in the max-pseudo sequentiality case.

4

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.

5

Limited Asynchronous Spiking Neural P Systems

Pan L., Wang J., Hoogeboom H.J.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

271-293

EN

In a biological system, if a long enough time interval is given, an enabled chemical reaction will finish its reaction in the given time interval. With this motivation, it is natural to impose a bound on the time intervalwhen an enabled spiking rule in a spiking neural P system (SN P system, for short) remains unused. In this work, a new working mode of SN P systems is defined, which is called limited asynchronous mode. In an SN P system working in limited asynchronous mode, if a rule is enabled at some step, this rule is not obligatorily used. From this step on, if the unused rule may be used later, it should be used in the given time interval. If further spikes make the rule non-applicable, then the computation continues in the new circumstances. The computation result of a computation in an SN P system working in limited asynchronous mode is defined as the total number of spikes sent into the environment by the system. It is proved that limited asynchronous SN P systems with standard spiking rules are universal. If the number of spikes present in each neuron of a limited asynchronous SN P system with standard spiking rules is bounded during a computation, then the power of a limited asynchronous SN P system with standard spiking rules falls drastically, and we get a characterization of semilinear sets of numbers.

6

Computing k-block Morphisms by Spiking Neural P Systems

Nishida T.Y.

Fundamenta Informaticae

|

2011

|

Vol. 111, nr 4

453-464

EN

In this paper we show that for every k-block morphism (k ≥ 2) there is a spiking neural P system which computes the morphism. This result generalises the result explored by G. Paun, M. Perez-Jimenez, and G. Rozenberg. We give an algorithm which constructs the spiking neural P system, that is, if a k-block morphism is given as an input, the algorithm makes rules of the spiking neural P system which computes the morphism.

7

Homogeneous Spiking Neural P Systems

Zeng X., Zhang X., Pan L.

Fundamenta Informaticae

|

2009

|

Vol. 97, nr 1/2

275-294

EN

Spiking neural P systems are a class of distributed parallel computing models inspired from the way the neurons communicate with each other by means of electrical impulses (called "spikes"). In this paper, we consider a restricted variant of spiking neural P systems, called homogeneous spiking neural P systems, where each neuron has the same set of rules. The universality of homogeneous spiking neural P systems is investigated. One of universality results is that it is sufficient for homogeneous spiking neural P system to have only one neuron that behaves nondeterministically in order to achieve Turing completeness.

8

Solving SUBSET SUM by Spiking Neural P Systems with Pre-computed Resources

Leporati A., Gutiérrez-Naranjo M.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 1

61-77

EN

Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre–computed resources are given in advance, provided that their structure is “regular” and they do not contain neither “hidden information” that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as SUBSET SUM. In particular, we first propose a semi–uniform family of spiking neural P systems in which every system solves a specific instance of SUBSET SUM. Then, we exploit a technique used to calculate ITERATED ADDITION with Boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve any instance of SUBSET SUM of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size.

9

Implementing Sorting Networks with Spiking Neural P Systems

Ceterchi R., Tomescu A.I.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 1

35-48

EN

Spiking neural P systems simulate the behavior of neurons sending signals through axons. Recently, some applications concerning Boolean circuits and sorting algorithms have been proposed. In this paper, we study the ability of such systems to simulate a well known parallel sorting model, sorting networks. First, we construct spiking neural P systems which act as comparators of two values, and then show how to assemble these building blocks according to the topology of a sorting network of N values. In the second part of the paper, we formalize a framework to transform any sorting network into a network composed of comparators which sort n values, 2 < n < N, having the same behaviour as the original sorting network, but using fewer neurons and synapses than the direct simulation. A comparison between the two models proposed here and the sorting model of Ionescu and Sburlan is also given.

10

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.