Wyniki wyszukiwania - Biblioteka Nauki

1

Homogeneous Spiking Neural P Systems

100%

Zeng X. , Zhang X. , Pan L.

Fundamenta Informaticae

|

2009

|

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

2

On String Languages Generated by Spiking Neural P Systems

100%

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

Fundamenta Informaticae

|

2007

|

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

3

Membrane Division, Oracles, and the Counting Hierarchy

100%

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

Fundamenta Informaticae

|

2015

|

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

4

On String Languages Generated by Spiking Neural P Systems with Astrocytes

100%

Kong Y. , Zhang Z. , Liu Y.

Fundamenta Informaticae

|

2015

|

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

5

Limited Asynchronous Spiking Neural P Systems

100%

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

Fundamenta Informaticae

|

2011

|

tom 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

Looking for Small Efficient P Systems

100%

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

Fundamenta Informaticae

|

2011

|

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

7

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

100%

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

Fundamenta Informaticae

|

2015

|

tom 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.τ

8

Small Universal Numerical P Systems with Thresholds for Computing Functions

100%

Liu L. , Yi W. , Yang Q. , Peng H. , Wang J.

Fundamenta Informaticae

|

2020

|

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

9

Membrane computing with external output

100%

Paun G. , Rozenberg G. , Salomaa A.

Fundamenta Informaticae

|

2000

|

tom Vol. 41, Nr 3

313-340

EN

A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include the computing power, normal forms, and basic decision problems.

10

Weighted Spiking Neural P Systems with Rules on Synapses

100%

Zhang X. , Zeng X. , Pan L.

Fundamenta Informaticae

|

2014

|

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

11

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

100%

Leporati A. , Gutiérrez-Naranjo M.

Fundamenta Informaticae

|

2008

|

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

12

Smaller Universal Spiking Neural P Systems

100%

Zhang X. , Zeng X. , Pan L.

Fundamenta Informaticae

|

2008

|

tom Vol. 87, nr 1

117-136

EN

The problem of finding small universal spiking neural P systems was recently investigated by Andrei P˘aun and Gheorghe P˘aun, for spiking neural P systems used as devices computing functions and as devices generating sets of numbers. For the first case, a universal spiking neural P system was produced by using 84 neurons for standard rules and using 49 neurons for extended rules. For spiking neural P systems used as generators of sets of numbers, a universal system with standard rules having 76 neurons, and one with extended rules having 50 neurons were obtained. In this paper, we continue the study of small universal spiking neural P systems and we improve in the number of neurons as follows. The small universal spiking neural P systems use 67 neurons for standard rules and 41 neurons for extended rules in the case of computing functions, and 63 neurons for standard rules and 41 neurons for extended rules in the case of generating sets of numbers.

13

(Tissue) P Systems with Unit Rules and Energy Assigned to Membranes

100%

Alhazov A. , Freund R. , Leporati A. , Oswald M. , Zandron C.

Fundamenta Informaticae

|

2006

|

tom Vol. 74, nr 4

391-408

EN

We introduce a new variant of membrane systems where the rules are directly assigned to membranes and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for systems working in the sequential mode with a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. On the other hand, when using the maximally parallel mode, we do not need a priority relation to obtain computational completeness. Finally, we introduce the corresponding model of tissue P systems with energy assigned to the membrane of each cell and objects moving from one cell to another one in the environment as well as being able to change the energy of a cell when entering or leaving the cell. In each derivation step, only one object may pass through the membrane of each cell. When using priorities on the rules in the sequential mode (where in each derivation step only one cell is affected) as well as without priorities in the maximally parallel mode (where in each derivation step all cells possible are affected) we again obtain computational completeness, whereas without priorities on the rules in the sequential mode we only get a characterization of the family of Parikh sets of languages generated by context-free matrix grammars.

14

Simulating Turing Machines by P Systems with External Output

100%

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

Fundamenta Informaticae

|

2002

|

tom 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].

15

On the Power of P Systems with DNA-Worm-Objects

100%

Maté J. L. , Rodriguez-Patón A. , Silva A.

Fundamenta Informaticae

|

2002

|

tom Vol. 49, nr 1-3

229-239

EN

We introduce a variant of P systems with string-objects - called worm-objects - inspired in the DNA computing area. These systems work with multisets of string-objects processed by splitting, mutation, replication and recombination. This model is simpler (we eliminate the replication operation) and more realistic (the recombination operation is changed by the simpler one of suffix-prefix or head-tail concatenation developed in the DNA computing framework) than the previous one. The result of a computation is the set of strings sent out of the system. We work with multisets of strings but we generate languages instead of sets of numbers. We prove that, without priority among rules or other control mechanisms, (1) these P systems with at most three membranes can generate all recursively enumerable languages, (2) with non-decreasing length mutation and splitting rules, three membranes are enough to generate the family of context-sensitive languages, and (3) with these restricted types of splitting and mutation rules, four membranes can generate the family of recursively enumerable languages.

16

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

100%

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

Fundamenta Informaticae

|

2015

|

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

17

Tissue P Systems with Small Cell Volume

100%

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

Fundamenta Informaticae

|

2017

|

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

18

Three Universal Homogeneous Spiking Neural P Systems Using Max Spike

100%

Păun A. , Sosík P.

Fundamenta Informaticae

|

2014

|

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

19

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

100%

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

Fundamenta Informaticae

|

2015

|

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

20

A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem

100%

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

Fundamenta Informaticae

|

2011

|

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