Wyniki wyszukiwania - Biblioteka Nauki

1

Three Universal Homogeneous Spiking Neural P Systems Using Max Spike

100%

Păun A. , Sosík P.

|

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.

2

P Systems Simulating Bacterial Conjugation : Universality and Properties

100%

Păun A. , Rodríguez-Patón A.

Fundamenta Informaticae

|

2017

|

tom Vol. 153, nr 1/2

87--103

EN

We refine the modeling in the P systems area of the way bacteria transmit genetic information in bacterial colonies, specifically the conjugation process. We study this new model from the computational power perspective using methods and ideas in the area; we are able to prove the universality of these systems. We show that systems working in a homogeneous manner and using only 75 species of objects in the regions and 13 species of "on-membrane" objects are enough for reaching universality. The system starts in a initial state with only few (nine) bacteria needed and the "bacteria" from this system are homogeneous, all have the same rules.

3

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

80%

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

Fundamenta Informaticae

|

2017

|

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

4

Results on Transforming NFA into DFCA

80%

Câmpeanu C. , Kari L. , Păun A.

|

2005

|

tom Vol. 64, nr 1-4

53-63

EN

In this paper we consider the transformation from (minimal) non-deterministic finite automata (NFAs) to deterministic finite cover automata (DFCAs). We want to compare the two equivalent accepting devices with respect to their number of states; this becomes in fact a comparison between the expression power of the nondeterministic device and the expression power of the deterministic with loops device. We prove a lower bound for the maximum state complexity of deterministic finite cover automata obtained from non-deterministic finite automata of a given state complexity n, considering the case of a binary alphabet. We show, for such binary alphabets, that the difference between maximum blow-up state complexity of DFA and DFCA can be as small as [..]compared to the number of states of the minimal DFA. Moreover, we show the structure of automata for worst case exponential blow-up complexity from NFA to DFCA. We conjecture that the lower bound given in the paper is also the upper bound. Several results clarifying some of the structure of the automata in the worst case are given (we strongly believe they will be pivotal in the upper bound proof).